route: Fix FIB next hop removal bug
refs: #2018
Change-Id: Id107c04d4cdce9cc756acad5d262e5c1e0cc29a8
diff --git a/src/route/fib.cpp b/src/route/fib.cpp
index 2010858..1815b27 100644
--- a/src/route/fib.cpp
+++ b/src/route/fib.cpp
@@ -24,14 +24,13 @@
#include <cmath>
#include <ndn-cxx/common.hpp>
-#include "nlsr.hpp"
+#include "adjacency-list.hpp"
+#include "conf-parameter.hpp"
#include "nexthop-list.hpp"
#include "face-map.hpp"
#include "fib.hpp"
#include "logger.hpp"
-
-
namespace nlsr {
INIT_LOGGER("Fib");
@@ -44,7 +43,7 @@
static bool
fibEntryNameCompare(const FibEntry& fibEntry, const ndn::Name& name)
{
- return fibEntry.getName() == name ;
+ return fibEntry.getName() == name;
}
void
@@ -93,84 +92,102 @@
}
void
-Fib::addNextHopsToFibEntryAndNfd(FibEntry& entry, NexthopList& nextHopList)
+Fib::addNextHopsToFibEntryAndNfd(FibEntry& entry, NexthopList& hopsToAdd)
{
const ndn::Name& name = entry.getName();
- nextHopList.sort();
-
- int numFaces = 0;
- int maxFaces = getNumberOfFacesForName(nextHopList,
- m_nlsr.getConfParameter().getMaxFacesPerPrefix());
-
- for (NexthopList::iterator hopIt = nextHopList.begin();
- hopIt != nextHopList.end() && numFaces < maxFaces; ++hopIt, ++numFaces)
+ for (NexthopList::iterator it = hopsToAdd.begin(); it != hopsToAdd.end(); ++it)
{
// Add nexthop to FIB entry
- entry.getNexthopList().addNextHop(*hopIt);
+ entry.getNexthopList().addNextHop(*it);
if (isPrefixUpdatable(name)) {
// Add nexthop to NDN-FIB
- registerPrefix(name, hopIt->getConnectingFaceUri(),
- hopIt->getRouteCostAsAdjustedInteger(),
+ registerPrefix(name, it->getConnectingFaceUri(),
+ it->getRouteCostAsAdjustedInteger(),
ndn::time::seconds(m_refreshTime + GRACE_PERIOD),
ndn::nfd::ROUTE_FLAG_CAPTURE, 0);
}
}
+
+ entry.getNexthopList().sort();
+}
+
+void
+Fib::removeOldNextHopsFromFibEntryAndNfd(FibEntry& entry, const NexthopList& installedHops)
+{
+ _LOG_DEBUG("Fib::removeOldNextHopsFromFibEntryAndNfd Called");
+
+ const ndn::Name& name = entry.getName();
+ NexthopList& entryHopList = entry.getNexthopList();
+
+ for (NexthopList::iterator it = entryHopList.begin(); it != entryHopList.end();) {
+
+ const std::string& faceUri = it->getConnectingFaceUri();
+
+ // See if the nexthop is installed in NFD's FIB
+ NexthopList::const_iterator foundIt = std::find_if(installedHops.cbegin(),
+ installedHops.cend(),
+ bind(&compareFaceUri, _1, faceUri));
+
+ // The next hop is not installed
+ if (foundIt == installedHops.cend()) {
+
+ if (isPrefixUpdatable(name)) {
+ // Remove the nexthop from NDN's FIB
+ unregisterPrefix(name, it->getConnectingFaceUri());
+ }
+
+ // Remove the next hop from the FIB entry
+ _LOG_DEBUG("Removing " << it->getConnectingFaceUri() << " from " << name);
+ // Since the iterator will be invalidated on removal, dereference the original
+ // and increment the copy
+ entryHopList.removeNextHop(*(it++));
+ }
+ else {
+ ++it;
+ }
+ }
}
void
-Fib::removeOldNextHopsFromFibEntryAndNfd(FibEntry& entry, NexthopList& newHopList)
+Fib::update(const ndn::Name& name, NexthopList& allHops)
{
- _LOG_DEBUG("Fib::removeOldNextHopsFromFibEntryAndNfd Called");
- const ndn::Name& name = entry.getName();
- NexthopList& entryHopList = entry.getNexthopList();
- NexthopList itHopList = entryHopList;
+ _LOG_DEBUG("Fib::update called");
- for (NexthopList::iterator it = itHopList.begin(); it != itHopList.end(); ++it) {
+ // Sort all of the next hops so lower cost hops are prioritized
+ allHops.sort();
- // See if the nexthop is in the new nexthop list
- const std::string& faceUri = it->getConnectingFaceUri();
- NexthopList::iterator foundIt = std::find_if(newHopList.begin(),
- newHopList.end(),
- bind(&compareFaceUri, _1, faceUri));
+ // Get the max possible faces which is the minumum of the configuration setting and
+ // the length of the list of all next hops.
+ unsigned int maxFaces = getNumberOfFacesForName(allHops);
- // The next hop is not in the new nexthop list
- if (foundIt == newHopList.end()) {
- // Remove the next hop from the FIB entry
- _LOG_DEBUG("Removing " << it->getConnectingFaceUri() << " from " << name);
- entryHopList.removeNextHop(*it);
+ NexthopList hopsToAdd;
+ unsigned int nFaces = 0;
- if (isPrefixUpdatable(name)) {
- // Remove the nexthop from NDN-FIB
- unregisterPrefix(name, it->getConnectingFaceUri());
- }
- }
- }
-}
-
-void
-Fib::update(const ndn::Name& name, NexthopList& nextHopList)
-{
- _LOG_DEBUG("Fib::updateFib Called");
+ // Create a list of next hops to be installed with length == maxFaces
+ for (NexthopList::iterator it = allHops.begin(); it != allHops.end() && nFaces < maxFaces;
+ ++it, ++nFaces)
+ {
+ hopsToAdd.addNextHop(*it);
+ }
std::list<FibEntry>::iterator entryIt = std::find_if(m_table.begin(),
m_table.end(),
bind(&fibEntryNameCompare, _1, name));
+
// New FIB entry
if (entryIt == m_table.end()) {
_LOG_DEBUG("New FIB Entry");
// Don't create an entry for a name with no nexthops
- if (nextHopList.getSize() == 0) {
+ if (hopsToAdd.getSize() == 0) {
return;
}
FibEntry entry(name);
- addNextHopsToFibEntryAndNfd(entry, nextHopList);
-
- entry.getNexthopList().sort();
+ addNextHopsToFibEntryAndNfd(entry, hopsToAdd);
// Set entry's expiration time point and sequence number
entry.setExpirationTimePoint(ndn::time::system_clock::now() +
@@ -189,15 +206,14 @@
FibEntry& entry = *entryIt;
// Remove empty FIB entry
- if (nextHopList.getSize() == 0) {
+ if (hopsToAdd.getSize() == 0) {
remove(name);
return;
}
- addNextHopsToFibEntryAndNfd(entry, nextHopList);
- removeOldNextHopsFromFibEntryAndNfd(entry, nextHopList);
+ addNextHopsToFibEntryAndNfd(entry, hopsToAdd);
- entry.getNexthopList().sort();
+ removeOldNextHopsFromFibEntryAndNfd(entry, hopsToAdd);
// Set entry's expiration time point
entry.setExpirationTimePoint(ndn::time::system_clock::now() +
@@ -205,7 +221,7 @@
// Increment sequence number
entry.setSeqNo(entry.getSeqNo() + 1);
- // Cancel previosuly scheduled event
+ // Cancel previously scheduled event
m_scheduler.cancelEvent(entry.getExpiringEventId());
// Schedule entry to be refreshed
@@ -234,23 +250,24 @@
}
}
-int
-Fib::getNumberOfFacesForName(NexthopList& nextHopList,
- uint32_t maxFacesPerPrefix)
+unsigned int
+Fib::getNumberOfFacesForName(NexthopList& nextHopList)
{
- int endFace = 0;
- if ((maxFacesPerPrefix == 0) || (nextHopList.getSize() <= maxFacesPerPrefix)) {
- return nextHopList.getSize();
+ uint32_t nNextHops = static_cast<uint32_t>(nextHopList.getNextHops().size());
+ uint32_t nMaxFaces = m_confParameter.getMaxFacesPerPrefix();
+
+ // Allow all faces
+ if (nMaxFaces == 0) {
+ return nNextHops;
}
else {
- return maxFacesPerPrefix;
+ return std::min(nNextHops, nMaxFaces);
}
- return endFace;
}
bool
Fib::isPrefixUpdatable(const ndn::Name& name) {
- if (!m_nlsr.getAdjacencyList().isNeighbor(name)) {
+ if (!m_adjacencyList.isNeighbor(name)) {
return true;
}
@@ -313,7 +330,7 @@
uint64_t faceCost, const ndn::time::milliseconds& timeout,
uint64_t flags, uint8_t times)
{
- uint64_t faceId = m_nlsr.getAdjacencyList().getFaceId(faceUri);
+ uint64_t faceId = m_adjacencyList.getFaceId(faceUri);
if (faceId != 0) {
ndn::nfd::ControlParameters faceParameters;
faceParameters
diff --git a/src/route/fib.hpp b/src/route/fib.hpp
index 9893ff2..e49727b 100644
--- a/src/route/fib.hpp
+++ b/src/route/fib.hpp
@@ -30,27 +30,30 @@
#include <ndn-cxx/util/time.hpp>
#include "face-map.hpp"
#include "fib-entry.hpp"
+#include "test-access-control.hpp"
namespace nlsr {
typedef ndn::function<void(const ndn::nfd::ControlParameters&)> CommandSucceedCallback;
typedef ndn::function<void(uint32_t/*code*/,const std::string&/*reason*/)> CommandFailCallback;
-class Nlsr;
-
+class AdjacencyList;
+class ConfParameter;
class Fib
{
public:
- Fib(Nlsr& nlsr, ndn::Face& face, ndn::Scheduler& scheduler)
- : m_nlsr(nlsr)
- , m_scheduler(scheduler)
+ Fib(ndn::Face& face, ndn::Scheduler& scheduler, AdjacencyList& adjacencyList, ConfParameter& conf)
+ : m_scheduler(scheduler)
, m_table()
, m_refreshTime(0)
, m_controller(face)
, m_faceMap()
+ , m_adjacencyList(adjacencyList)
+ , m_confParameter(conf)
{
}
+
~Fib()
{
}
@@ -59,7 +62,7 @@
remove(const ndn::Name& name);
void
- update(const ndn::Name& name, NexthopList& nextHopList);
+ update(const ndn::Name& name, NexthopList& allHops);
void
clean();
@@ -75,17 +78,17 @@
isPrefixUpdatable(const ndn::Name& name);
void
- addNextHopsToFibEntryAndNfd(FibEntry& entry, NexthopList& nextHopList);
+ addNextHopsToFibEntryAndNfd(FibEntry& entry, NexthopList& hopsToAdd);
void
- removeOldNextHopsFromFibEntryAndNfd(FibEntry& entry, NexthopList& newHopList);
+ removeOldNextHopsFromFibEntryAndNfd(FibEntry& entry, const NexthopList& installedHops);
void
removeHop(NexthopList& nl, const std::string& doNotRemoveHopFaceUri,
const ndn::Name& name);
- int
- getNumberOfFacesForName(NexthopList& nextHopList, uint32_t maxFacesPerPrefix);
+ unsigned int
+ getNumberOfFacesForName(NexthopList& nextHopList);
ndn::EventId
scheduleEntryExpiration(const ndn::Name& name, int32_t feSeqNum,
@@ -178,14 +181,19 @@
const std::string& message);
private:
- Nlsr& m_nlsr;
ndn::Scheduler& m_scheduler;
std::list<FibEntry> m_table;
int32_t m_refreshTime;
ndn::nfd::Controller m_controller;
+
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
FaceMap m_faceMap;
+private:
+ AdjacencyList& m_adjacencyList;
+ ConfParameter& m_confParameter;
+
static const uint64_t GRACE_PERIOD;
};
diff --git a/src/route/nexthop-list.hpp b/src/route/nexthop-list.hpp
index 7c2011e..faf13f0 100644
--- a/src/route/nexthop-list.hpp
+++ b/src/route/nexthop-list.hpp
@@ -73,6 +73,7 @@
}
typedef std::list<NextHop>::iterator iterator;
+ typedef std::list<NextHop>::const_iterator const_iterator;
iterator
begin()
@@ -86,6 +87,18 @@
return m_nexthopList.end();
}
+ const_iterator
+ cbegin() const
+ {
+ return m_nexthopList.begin();
+ }
+
+ const_iterator
+ cend() const
+ {
+ return m_nexthopList.end();
+ }
+
void
writeLog();