rib: Generate FIB updates using route flags
refs: #1325
Change-Id: I5c567da1c06819caeba5cc5b024914666ba70ab6
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)
{