Separating interface and implementation of FIB. Right now everything is
kind of broken.
diff --git a/apps/ccnx-producer.cc b/apps/ccnx-producer.cc
index bad9ee9..73ab8b7 100644
--- a/apps/ccnx-producer.cc
+++ b/apps/ccnx-producer.cc
@@ -30,6 +30,7 @@
#include "ns3/ccnx-app-face.h"
#include "ns3/ccnx-fib.h"
+#include "../model/ccnx-fib-impl.h"
#include <boost/ref.hpp>
#include <boost/lambda/lambda.hpp>
@@ -84,12 +85,12 @@
CcnxApp::StartApplication ();
Ptr<CcnxFib> fib = GetNode ()->GetObject<CcnxFib> ();
- CcnxFibEntryContainer::type::iterator fibEntry = fib->Add (m_prefix, m_face, 0);
+ CcnxFib::iterator fibEntry = fib->Add (m_prefix, m_face, 0);
// make face green, so it will be used primarily
- fib->m_fib.modify (fibEntry,
- ll::bind (&CcnxFibEntry::UpdateStatus,
- ll::_1, m_face, CcnxFibFaceMetric::NDN_FIB_GREEN));
+ StaticCast<CcnxFibImpl> (fib)->modify (fibEntry,
+ ll::bind (&CcnxFibEntry::UpdateStatus,
+ ll::_1, m_face, CcnxFibFaceMetric::NDN_FIB_GREEN));
}
void
diff --git a/model/ccnx-fib-entry.cc b/model/ccnx-fib-entry.cc
new file mode 100644
index 0000000..c0c575a
--- /dev/null
+++ b/model/ccnx-fib-entry.cc
@@ -0,0 +1,185 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "ccnx-fib-entry.h"
+
+#include "ns3/ccnx-name-components.h"
+#include "ns3/log.h"
+
+#define NDN_RTO_ALPHA 0.125
+#define NDN_RTO_BETA 0.25
+#define NDN_RTO_K 4
+
+#include <boost/ref.hpp>
+#include <boost/lambda/lambda.hpp>
+#include <boost/lambda/bind.hpp>
+namespace ll = boost::lambda;
+
+NS_LOG_COMPONENT_DEFINE ("CcnxFibEntry");
+
+namespace ns3
+{
+
+//////////////////////////////////////////////////////////////////////
+// Helpers
+//////////////////////////////////////////////////////////////////////
+namespace __ccnx_private {
+
+struct CcnxFibFaceMetricByFace
+{
+ typedef CcnxFibFaceMetricContainer::type::index<i_face>::type
+ type;
+};
+
+}
+//////////////////////////////////////////////////////////////////////
+//////////////////////////////////////////////////////////////////////
+
+using namespace __ccnx_private;
+
+void
+CcnxFibFaceMetric::UpdateRtt (const Time &rttSample)
+{
+ // const Time & this->m_rttSample
+
+ //update srtt and rttvar (RFC 2988)
+ if (m_sRtt.IsZero ())
+ {
+ //first RTT measurement
+ NS_ASSERT_MSG (m_rttVar.IsZero (), "SRTT is zero, but variation is not");
+
+ m_sRtt = rttSample;
+ m_rttVar = Time (m_sRtt / 2.0);
+ }
+ else
+ {
+ m_rttVar = Time ((1 - NDN_RTO_BETA) * m_rttVar + NDN_RTO_BETA * Abs(m_sRtt - rttSample));
+ m_sRtt = Time ((1 - NDN_RTO_ALPHA) * m_sRtt + NDN_RTO_ALPHA * rttSample);
+ }
+}
+
+/////////////////////////////////////////////////////////////////////
+
+void
+CcnxFibEntry::UpdateFaceRtt (Ptr<CcnxFace> face, const Time &sample)
+{
+ CcnxFibFaceMetricByFace::type::iterator record = m_faces.get<i_face> ().find (face);
+ NS_ASSERT_MSG (record != m_faces.get<i_face> ().end (),
+ "Update status can be performed only on existing faces of CcxnFibEntry");
+
+ m_faces.modify (record,
+ ll::bind (&CcnxFibFaceMetric::UpdateRtt, ll::_1, sample));
+
+ // reordering random access index same way as by metric index
+ m_faces.get<i_nth> ().rearrange (m_faces.get<i_metric> ().begin ());
+}
+
+void
+CcnxFibEntry::UpdateStatus (Ptr<CcnxFace> face, CcnxFibFaceMetric::Status status)
+{
+ NS_LOG_FUNCTION (this << boost::cref(*face) << status);
+
+ CcnxFibFaceMetricByFace::type::iterator record = m_faces.get<i_face> ().find (face);
+ NS_ASSERT_MSG (record != m_faces.get<i_face> ().end (),
+ "Update status can be performed only on existing faces of CcxnFibEntry");
+
+ m_faces.modify (record,
+ (&ll::_1)->*&CcnxFibFaceMetric::m_status = status);
+
+ // reordering random access index same way as by metric index
+ m_faces.get<i_nth> ().rearrange (m_faces.get<i_metric> ().begin ());
+}
+
+void
+CcnxFibEntry::AddOrUpdateRoutingMetric (Ptr<CcnxFace> face, int32_t metric)
+{
+ NS_LOG_FUNCTION (this);
+ NS_ASSERT_MSG (face != NULL, "Trying to Add or Update NULL face");
+
+ CcnxFibFaceMetricByFace::type::iterator record = m_faces.get<i_face> ().find (face);
+ if (record == m_faces.get<i_face> ().end ())
+ {
+ m_faces.insert (CcnxFibFaceMetric (face, metric));
+ }
+ else
+ {
+ // don't update metric to higher value
+ if (record->m_routingCost > metric || record->m_status == CcnxFibFaceMetric::NDN_FIB_RED)
+ {
+ m_faces.modify (record,
+ (&ll::_1)->*&CcnxFibFaceMetric::m_routingCost = metric);
+
+ m_faces.modify (record,
+ (&ll::_1)->*&CcnxFibFaceMetric::m_status = CcnxFibFaceMetric::NDN_FIB_YELLOW);
+ }
+ }
+
+ // reordering random access index same way as by metric index
+ m_faces.get<i_nth> ().rearrange (m_faces.get<i_metric> ().begin ());
+}
+
+void
+CcnxFibEntry::Invalidate ()
+{
+ for (CcnxFibFaceMetricByFace::type::iterator face = m_faces.begin ();
+ face != m_faces.end ();
+ face++)
+ {
+ m_faces.modify (face,
+ (&ll::_1)->*&CcnxFibFaceMetric::m_routingCost = std::numeric_limits<uint16_t>::max ());
+
+ m_faces.modify (face,
+ (&ll::_1)->*&CcnxFibFaceMetric::m_status = CcnxFibFaceMetric::NDN_FIB_RED);
+ }
+}
+
+const CcnxFibFaceMetric &
+CcnxFibEntry::FindBestCandidate (uint32_t skip/* = 0*/) const
+{
+ if (m_faces.size () == 0) throw CcnxFibEntry::NoFaces ();
+ skip = skip % m_faces.size();
+ return m_faces.get<i_nth> () [skip];
+}
+
+std::ostream& operator<< (std::ostream& os, const CcnxFibEntry &entry)
+{
+ for (CcnxFibFaceMetricContainer::type::index<i_nth>::type::iterator metric =
+ entry.m_faces.get<i_nth> ().begin ();
+ metric != entry.m_faces.get<i_nth> ().end ();
+ metric++)
+ {
+ if (metric != entry.m_faces.get<i_nth> ().begin ())
+ os << ", ";
+
+ os << *metric;
+ }
+ return os;
+}
+
+std::ostream& operator<< (std::ostream& os, const CcnxFibFaceMetric &metric)
+{
+ static const std::string statusString[] = {"","g","y","r"};
+
+ os << *metric.m_face << "(" << metric.m_routingCost << ","<< statusString [metric.m_status] << "," << metric.m_face->GetMetric () << ")";
+ return os;
+}
+
+
+} // ns3
diff --git a/model/ccnx-fib-entry.h b/model/ccnx-fib-entry.h
new file mode 100644
index 0000000..9aa75cb
--- /dev/null
+++ b/model/ccnx-fib-entry.h
@@ -0,0 +1,237 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef _CCNX_FIB_ENTRY_H_
+#define _CCNX_FIB_ENTRY_H_
+
+#include "ns3/ptr.h"
+#include "ns3/nstime.h"
+#include "ns3/ccnx.h"
+#include "ns3/ccnx-face.h"
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/tag.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/multi_index/composite_key.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/random_access_index.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/mem_fun.hpp>
+
+namespace ns3
+{
+
+class CcnxNameComponents;
+
+/**
+ * \ingroup ccnx
+ * \brief Structure holding various parameters associated with a (FibEntry, Face) tuple
+ */
+class CcnxFibFaceMetric
+{
+public:
+ /**
+ * @brief Color codes for FIB face status
+ */
+ enum Status { NDN_FIB_GREEN = 1,
+ NDN_FIB_YELLOW = 2,
+ NDN_FIB_RED = 3 };
+public:
+ /**
+ * \brief Metric constructor
+ *
+ * \param face Face for which metric
+ * \param cost Initial value for routing cost
+ */
+ CcnxFibFaceMetric (Ptr<CcnxFace> face, int32_t cost)
+ : m_face (face)
+ , m_status (NDN_FIB_YELLOW)
+ , m_routingCost (cost)
+ , m_sRtt (Seconds (0))
+ , m_rttVar (Seconds (0))
+ { }
+
+ /**
+ * \brief Comparison operator used by boost::multi_index::identity<>
+ */
+ bool
+ operator< (const CcnxFibFaceMetric &fm) const { return *m_face < *fm.m_face; } // return identity of the face
+
+ /**
+ * @brief Comparison between CcnxFibFaceMetric and CcnxFace
+ */
+ bool
+ operator< (const Ptr<CcnxFace> &face) const { return *m_face < *face; }
+
+ /**
+ * @brief Return CcnxFace associated with CcnxFibFaceMetric
+ */
+ Ptr<CcnxFace>
+ GetFace () const { return m_face; }
+
+ /**
+ * \brief Recalculate smoothed RTT and RTT variation
+ * \param rttSample RTT sample
+ */
+ void
+ UpdateRtt (const Time &rttSample);
+
+private:
+ friend std::ostream& operator<< (std::ostream& os, const CcnxFibFaceMetric &metric);
+public:
+ Ptr<CcnxFace> m_face; ///< Face
+
+ Status m_status; ///< \brief Status of the next hop:
+ ///< - NDN_FIB_GREEN
+ ///< - NDN_FIB_YELLOW
+ ///< - NDN_FIB_RED
+
+ int32_t m_routingCost; ///< \brief routing protocol cost (interpretation of the value depends on the underlying routing protocol)
+
+ Time m_sRtt; ///< \brief smoothed round-trip time
+ Time m_rttVar; ///< \brief round-trip time variation
+};
+
+/**
+ * \ingroup ccnx
+ * \brief Typedef for indexed face container of CcnxFibEntry
+ *
+ * Currently, there are 2 indexes:
+ * - by face (used to find record and update metric)
+ * - by metric (face ranking)
+ * - random access index (for fast lookup on nth face). Order is
+ * maintained manually to be equal to the 'by metric' order
+ */
+struct CcnxFibFaceMetricContainer
+{
+ /// @cond include_hidden
+ typedef boost::multi_index::multi_index_container<
+ CcnxFibFaceMetric,
+ boost::multi_index::indexed_by<
+ // For fast access to elements using CcnxFace
+ boost::multi_index::ordered_unique<
+ boost::multi_index::tag<__ccnx_private::i_face>,
+ boost::multi_index::member<CcnxFibFaceMetric,Ptr<CcnxFace>,&CcnxFibFaceMetric::m_face>
+ >,
+
+ // List of available faces ordered by (status, m_routingCost)
+ boost::multi_index::ordered_non_unique<
+ boost::multi_index::tag<__ccnx_private::i_metric>,
+ boost::multi_index::composite_key<
+ CcnxFibFaceMetric,
+ boost::multi_index::member<CcnxFibFaceMetric,CcnxFibFaceMetric::Status,&CcnxFibFaceMetric::m_status>,
+ boost::multi_index::member<CcnxFibFaceMetric,int32_t,&CcnxFibFaceMetric::m_routingCost>
+ >
+ >,
+
+ // To optimize nth candidate selection (sacrifice a little bit space to gain speed)
+ boost::multi_index::random_access<
+ boost::multi_index::tag<__ccnx_private::i_nth>
+ >
+ >
+ > type;
+ /// @endcond
+};
+
+/**
+ * \ingroup ccnx
+ * \brief Structure for FIB table entry, holding indexed list of
+ * available faces and their respective metrics
+ */
+class CcnxFibEntry : public SimpleRefCount<CcnxFibEntry>
+{
+public:
+ class NoFaces {}; ///< @brief Exception class for the case when FIB entry is not found
+
+ /**
+ * \brief Constructor
+ * \param prefix smart pointer to the prefix for the FIB entry
+ */
+ CcnxFibEntry (const Ptr<const CcnxNameComponents> &prefix)
+ : m_prefix (prefix)
+ , m_needsProbing (false)
+ { }
+
+ /**
+ * \brief Update status of FIB next hop
+ * \param status Status to set on the FIB entry
+ */
+ void UpdateStatus (Ptr<CcnxFace> face, CcnxFibFaceMetric::Status status);
+
+ /**
+ * \brief Add or update routing metric of FIB next hop
+ *
+ * Initial status of the next hop is set to YELLOW
+ */
+ void AddOrUpdateRoutingMetric (Ptr<CcnxFace> face, int32_t metric);
+
+ /**
+ * @brief Invalidate face
+ *
+ * Set routing metric on all faces to max and status to RED
+ */
+ void
+ Invalidate ();
+
+ /**
+ * @brief Update RTT averages for the face
+ */
+ void
+ UpdateFaceRtt (Ptr<CcnxFace> face, const Time &sample);
+
+ /**
+ * \brief Get prefix for the FIB entry
+ */
+ const CcnxNameComponents&
+ GetPrefix () const { return *m_prefix; }
+
+ /**
+ * \brief Find "best route" candidate, skipping `skip' first candidates (modulo # of faces)
+ *
+ * throws CcnxFibEntry::NoFaces if m_faces.size()==0
+ */
+ const CcnxFibFaceMetric &
+ FindBestCandidate (uint32_t skip = 0) const;
+
+ /**
+ * @brief Remove record associated with `face`
+ */
+ void
+ RemoveFace (const Ptr<CcnxFace> &face)
+ {
+ m_faces.erase (face);
+ }
+
+private:
+ friend std::ostream& operator<< (std::ostream& os, const CcnxFibEntry &entry);
+
+public:
+ Ptr<const CcnxNameComponents> m_prefix; ///< \brief Prefix of the FIB entry
+ CcnxFibFaceMetricContainer::type m_faces; ///< \brief Indexed list of faces
+
+ bool m_needsProbing; ///< \brief flag indicating that probing should be performed
+};
+
+std::ostream& operator<< (std::ostream& os, const CcnxFibEntry &entry);
+std::ostream& operator<< (std::ostream& os, const CcnxFibFaceMetric &metric);
+
+} // ns3
+
+#endif // _CCNX_FIB_ENTRY_H_
diff --git a/model/ccnx-fib-impl.cc b/model/ccnx-fib-impl.cc
new file mode 100644
index 0000000..18d07ad
--- /dev/null
+++ b/model/ccnx-fib-impl.cc
@@ -0,0 +1,179 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "ccnx-fib-impl.h"
+
+#include "ccnx.h"
+#include "ccnx-face.h"
+#include "ccnx-interest-header.h"
+
+#include "ns3/node.h"
+#include "ns3/assert.h"
+#include "ns3/names.h"
+#include "ns3/log.h"
+
+#include <boost/ref.hpp>
+#include <boost/lambda/lambda.hpp>
+#include <boost/lambda/bind.hpp>
+namespace ll = boost::lambda;
+
+NS_LOG_COMPONENT_DEFINE ("CcnxFibImpl");
+
+namespace ns3 {
+
+NS_OBJECT_ENSURE_REGISTERED (CcnxFibImpl);
+
+TypeId
+CcnxFibImpl::GetTypeId (void)
+{
+ static TypeId tid = TypeId ("ns3::CcnxFib") // cheating ns3 object system
+ .SetParent<Object> ()
+ .SetGroupName ("Ccnx")
+ .AddConstructor<CcnxFibImpl> ()
+ ;
+ return tid;
+}
+
+CcnxFibImpl::CcnxFibImpl ()
+{
+}
+
+void
+CcnxFibImpl::NotifyNewAggregate ()
+{
+ Object::NotifyNewAggregate ();
+}
+
+void
+CcnxFibImpl::DoDispose (void)
+{
+ clear ();
+ Object::DoDispose ();
+}
+
+
+CcnxFib::iterator
+CcnxFibImpl::LongestPrefixMatch (const CcnxInterestHeader &interest) const
+{
+ super::iterator item = const_cast<CcnxFibImpl*> (this)->super::longest_prefix_match (interest.GetName ());
+ // @todo use predicate to search with exclude filters
+
+ if (item == super::end ())
+ return 0;
+ else
+ return item->payload ();
+}
+
+
+CcnxFib::iterator
+CcnxFibImpl::Add (const CcnxNameComponents &prefix, Ptr<CcnxFace> face, int32_t metric)
+{
+ return Add (Create<CcnxNameComponents> (prefix), face, metric);
+}
+
+CcnxFib::iterator
+CcnxFibImpl::Add (const Ptr<const CcnxNameComponents> &prefix, Ptr<CcnxFace> face, int32_t metric)
+{
+ NS_LOG_FUNCTION(this->GetObject<Node> ()->GetId () << boost::cref(*prefix) << boost::cref(*face) << metric);
+
+ // will add entry if doesn't exists, or just return an iterator to the existing entry
+ std::pair< super::iterator, bool > result = super::insert (*prefix, Create<CcnxFibEntry> (prefix));
+
+ NS_ASSERT_MSG (face != NULL, "Trying to modify NULL face");
+
+ super::modify (result.first,
+ ll::bind (&CcnxFibEntry::AddOrUpdateRoutingMetric, ll::_1, face, metric));
+
+ return result.first->payload ();
+}
+
+void
+CcnxFibImpl::Remove (const Ptr<const CcnxNameComponents> &prefix)
+{
+ NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
+
+ super::erase (*prefix);
+}
+
+void
+CcnxFibImpl::Invalidate (const Ptr<const CcnxNameComponents> &prefix)
+{
+ NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
+
+ super::iterator foundItem, lastItem;
+ bool reachLast;
+ boost::tie (foundItem, reachLast, lastItem) = super::getTrie ().find (*prefix);
+
+ if (!reachLast || lastItem->payload () == 0)
+ return; // nothing to invalidate
+
+ super::modify (lastItem,
+ ll::bind (&CcnxFibEntry::Invalidate, ll::_1));
+}
+
+void
+CcnxFibImpl::InvalidateAll ()
+{
+ // NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId ());
+
+ // for (super::iterator entry = m_fib.begin ();
+ // entry != m_fib.end ();
+ // entry ++)
+ // {
+ // m_fib.modify (entry,
+ // ll::bind (&CcnxFibEntry::Invalidate, ll::_1));
+ // }
+}
+
+void
+CcnxFibImpl::Remove (const CcnxFibEntry &entry, Ptr<CcnxFace> face)
+{
+ // NS_LOG_FUNCTION (this);
+
+ // m_fib.modify (m_fib.iterator_to (entry),
+ // ll::bind (&CcnxFibEntry::RemoveFace, ll::_1, face));
+ // if (entry.m_faces.size () == 0)
+ // {
+ // m_fib.erase (m_fib.iterator_to (entry));
+ // }
+}
+
+void
+CcnxFibImpl::RemoveFromAll (Ptr<CcnxFace> face)
+{
+ // NS_LOG_FUNCTION (this);
+
+ // for_each (m_fib.begin (), m_fib.end (),
+ // ll::bind (static_cast< void (CcnxFib::*) (const CcnxFibEntry &, Ptr<CcnxFace>) > (&CcnxFib::Remove),
+ // this, ll::_1, face));
+}
+
+void
+CcnxFibImpl::Print (std::ostream &os) const
+{
+ // for (super::iterator entry = fib.m_fib.begin ();
+ // entry != fib.m_fib.end ();
+ // entry++)
+ // {
+ // os << entry->GetPrefix () << "\t" << *entry << "\n";
+ // }
+}
+
+} // namespace ns3
diff --git a/model/ccnx-fib-impl.h b/model/ccnx-fib-impl.h
new file mode 100644
index 0000000..b10d558
--- /dev/null
+++ b/model/ccnx-fib-impl.h
@@ -0,0 +1,166 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef _CCNX_FIB_IMPL_H_
+#define _CCNX_FIB_IMPL_H_
+
+#include "ns3/ccnx-fib.h"
+#include "ns3/ccnx-name-components.h"
+
+#include "../utils/trie-with-policy.h"
+#include "../utils/empty-policy.h"
+
+namespace ns3 {
+
+struct CcnxFibEntryContainer
+{
+ typedef ndnSIM::trie_with_policy<
+ CcnxNameComponents,
+ ndnSIM::smart_pointer_payload_traits<CcnxFibEntry>,
+ ndnSIM::empty_policy_traits
+ > type;
+};
+
+/**
+ * \ingroup ccnx
+ * \brief Class implementing FIB functionality
+ */
+class CcnxFibImpl : public CcnxFib,
+ private CcnxFibEntryContainer::type
+{
+public:
+ typedef CcnxFibEntryContainer::type super;
+
+ /**
+ * \brief Interface ID
+ *
+ * \return interface ID
+ */
+ static TypeId GetTypeId ();
+
+ /**
+ * \brief Constructor
+ */
+ CcnxFibImpl ();
+
+ /**
+ * \brief Perform longest prefix match
+ *
+ * \todo Implement exclude filters
+ *
+ * \param interest Interest packet header
+ * \returns If entry found a valid iterator will be returned, otherwise end ()
+ */
+ CcnxFib::iterator
+ LongestPrefixMatch (const CcnxInterestHeader &interest) const;
+
+ /**
+ * \brief Add or update FIB entry
+ *
+ * If the entry exists, metric will be updated. Otherwise, new entry will be created
+ *
+ * Entries in FIB never deleted. They can be invalidated with metric==NETWORK_UNREACHABLE
+ *
+ * @param name Prefix
+ * @param face Forwarding face
+ * @param metric Routing metric
+ */
+ CcnxFib::iterator
+ Add (const CcnxNameComponents &prefix, Ptr<CcnxFace> face, int32_t metric);
+
+ /**
+ * \brief Add or update FIB entry using smart pointer to prefix
+ *
+ * If the entry exists, metric will be updated. Otherwise, new entry will be created
+ *
+ * Entries in FIB never deleted. They can be invalidated with metric==NETWORK_UNREACHABLE
+ *
+ * @param name Smart pointer to prefix
+ * @param face Forwarding face
+ * @param metric Routing metric
+ */
+ CcnxFib::iterator
+ Add (const Ptr<const CcnxNameComponents> &prefix, Ptr<CcnxFace> face, int32_t metric);
+
+ /**
+ * @brief Remove FIB entry
+ *
+ * ! ATTENTION ! Use with caution. All PIT entries referencing the corresponding FIB entry will become invalid.
+ * So, simulation may crash.
+ *
+ * @param name Smart pointer to prefix
+ */
+ void
+ Remove (const Ptr<const CcnxNameComponents> &prefix);
+
+ /**
+ * @brief Invalidate FIB entry ("Safe" version of Remove)
+ *
+ * All faces for the entry will be assigned maximum routing metric and NDN_FIB_RED status
+ * @param name Smart pointer to prefix
+ */
+ void
+ Invalidate (const Ptr<const CcnxNameComponents> &prefix);
+
+ /**
+ * @brief Invalidate all FIB entries
+ */
+ void
+ InvalidateAll ();
+
+ /**
+ * @brief Remove reference to a face from the entry. If entry had only this face, the whole
+ * entry will be removed
+ */
+ void
+ Remove (const CcnxFibEntry &entry, Ptr<CcnxFace> face);
+
+ /**
+ * @brief Remove all references to a face from FIB. If for some enty that face was the only element,
+ * this FIB entry will be removed.
+ */
+ void
+ RemoveFromAll (Ptr<CcnxFace> face);
+
+ void
+ Print (std::ostream &os) const;
+
+ /**
+ * @brief Modify element in container
+ */
+ template<typename Modifier>
+ bool
+ modify (CcnxFib::iterator position, Modifier mod)
+ {
+ return this->modify (position, mod);
+ }
+
+protected:
+ // inherited from Object class
+ virtual void NotifyNewAggregate (); ///< @brief Notify when object is aggregated
+ virtual void DoDispose (); ///< @brief Perform cleanup
+
+private:
+ Ptr<Node> m_node;
+};
+
+} // namespace ns3
+
+#endif /* _CCNX_FIB_IMPL_H_ */
diff --git a/model/ccnx-fib.cc b/model/ccnx-fib.cc
index 4159f73..5bbbc15 100644
--- a/model/ccnx-fib.cc
+++ b/model/ccnx-fib.cc
@@ -24,336 +24,29 @@
#include "ccnx-face.h"
#include "ccnx-interest-header.h"
-#include "ns3/node.h"
-#include "ns3/assert.h"
-#include "ns3/names.h"
-#include "ns3/log.h"
+#include "ccnx-name-components.h"
+#include "ccnx-fib-impl.h"
-#define NDN_RTO_ALPHA 0.125
-#define NDN_RTO_BETA 0.25
-#define NDN_RTO_K 4
+#include "ns3/node.h"
+#include "ns3/names.h"
#include <boost/ref.hpp>
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
namespace ll = boost::lambda;
-NS_LOG_COMPONENT_DEFINE ("CcnxFib");
-
namespace ns3 {
-NS_OBJECT_ENSURE_REGISTERED (CcnxFib);
-
-//////////////////////////////////////////////////////////////////////
-// Helpers
-//////////////////////////////////////////////////////////////////////
-namespace __ccnx_private {
-
-struct CcnxFibFaceMetricByFace
-{
- typedef CcnxFibFaceMetricContainer::type::index<i_face>::type
- type;
-};
-
-}
-//////////////////////////////////////////////////////////////////////
-//////////////////////////////////////////////////////////////////////
-
using namespace __ccnx_private;
-TypeId
-CcnxFib::GetTypeId (void)
-{
- static TypeId tid = TypeId ("ns3::CcnxFib")
- .SetParent<Object> ()
- .SetGroupName ("Ccnx")
- .AddConstructor<CcnxFib> ()
-
- ;
- return tid;
-}
-
-/////////////////////////////////////////////////////////////////////
-
-void
-CcnxFibFaceMetric::UpdateRtt (const Time &rttSample)
-{
- // const Time & this->m_rttSample
-
- //update srtt and rttvar (RFC 2988)
- if (m_sRtt.IsZero ())
- {
- //first RTT measurement
- NS_ASSERT_MSG (m_rttVar.IsZero (), "SRTT is zero, but variation is not");
-
- m_sRtt = rttSample;
- m_rttVar = Time (m_sRtt / 2.0);
- }
- else
- {
- m_rttVar = Time ((1 - NDN_RTO_BETA) * m_rttVar + NDN_RTO_BETA * Abs(m_sRtt - rttSample));
- m_sRtt = Time ((1 - NDN_RTO_ALPHA) * m_sRtt + NDN_RTO_ALPHA * rttSample);
- }
-}
-
-/////////////////////////////////////////////////////////////////////
-
-void
-CcnxFibEntry::UpdateFaceRtt (Ptr<CcnxFace> face, const Time &sample)
-{
- CcnxFibFaceMetricByFace::type::iterator record = m_faces.get<i_face> ().find (face);
- NS_ASSERT_MSG (record != m_faces.get<i_face> ().end (),
- "Update status can be performed only on existing faces of CcxnFibEntry");
-
- m_faces.modify (record,
- ll::bind (&CcnxFibFaceMetric::UpdateRtt, ll::_1, sample));
-
- // reordering random access index same way as by metric index
- m_faces.get<i_nth> ().rearrange (m_faces.get<i_metric> ().begin ());
-}
-
-void
-CcnxFibEntry::UpdateStatus (Ptr<CcnxFace> face, CcnxFibFaceMetric::Status status)
-{
- NS_LOG_FUNCTION (this << boost::cref(*face) << status);
-
- CcnxFibFaceMetricByFace::type::iterator record = m_faces.get<i_face> ().find (face);
- NS_ASSERT_MSG (record != m_faces.get<i_face> ().end (),
- "Update status can be performed only on existing faces of CcxnFibEntry");
-
- m_faces.modify (record,
- (&ll::_1)->*&CcnxFibFaceMetric::m_status = status);
-
- // reordering random access index same way as by metric index
- m_faces.get<i_nth> ().rearrange (m_faces.get<i_metric> ().begin ());
-}
-
-void
-CcnxFibEntry::AddOrUpdateRoutingMetric (Ptr<CcnxFace> face, int32_t metric)
-{
- NS_LOG_FUNCTION (this);
- NS_ASSERT_MSG (face != NULL, "Trying to Add or Update NULL face");
-
- CcnxFibFaceMetricByFace::type::iterator record = m_faces.get<i_face> ().find (face);
- if (record == m_faces.get<i_face> ().end ())
- {
- m_faces.insert (CcnxFibFaceMetric (face, metric));
- }
- else
- {
- // don't update metric to higher value
- if (record->m_routingCost > metric || record->m_status == CcnxFibFaceMetric::NDN_FIB_RED)
- {
- m_faces.modify (record,
- (&ll::_1)->*&CcnxFibFaceMetric::m_routingCost = metric);
-
- m_faces.modify (record,
- (&ll::_1)->*&CcnxFibFaceMetric::m_status = CcnxFibFaceMetric::NDN_FIB_YELLOW);
- }
- }
-
- // reordering random access index same way as by metric index
- m_faces.get<i_nth> ().rearrange (m_faces.get<i_metric> ().begin ());
-}
-
-void
-CcnxFibEntry::Invalidate ()
-{
- for (CcnxFibFaceMetricByFace::type::iterator face = m_faces.begin ();
- face != m_faces.end ();
- face++)
- {
- m_faces.modify (face,
- (&ll::_1)->*&CcnxFibFaceMetric::m_routingCost = std::numeric_limits<uint16_t>::max ());
-
- m_faces.modify (face,
- (&ll::_1)->*&CcnxFibFaceMetric::m_status = CcnxFibFaceMetric::NDN_FIB_RED);
- }
-}
-
-const CcnxFibFaceMetric &
-CcnxFibEntry::FindBestCandidate (uint32_t skip/* = 0*/) const
-{
- if (m_faces.size () == 0) throw CcnxFibEntry::NoFaces ();
- skip = skip % m_faces.size();
- return m_faces.get<i_nth> () [skip];
-}
-
-
-CcnxFib::CcnxFib ()
-{
-}
-
-void
-CcnxFib::NotifyNewAggregate ()
-{
- if (m_node == 0)
- m_node = this->GetObject<Node>();
- Object::NotifyNewAggregate ();
-}
-
-void
-CcnxFib::DoDispose (void)
-{
- m_fib.clear ();
- m_node = 0;
- Object::DoDispose ();
-}
-
-
-CcnxFibEntryContainer::type::iterator
-CcnxFib::LongestPrefixMatch (const CcnxInterestHeader &interest) const
-{
- const CcnxNameComponents &name = interest.GetName ();
- for (size_t componentsCount = name.GetComponents ().size ()+1;
- componentsCount > 0;
- componentsCount--)
- {
- CcnxNameComponents subPrefix (name.GetSubComponents (componentsCount-1));
- CcnxFibEntryContainer::type::iterator match = m_fib.find (subPrefix);
- if (match != m_fib.end())
- return match;
- }
-
- return m_fib.end ();
-}
-
-
-CcnxFibEntryContainer::type::iterator
-CcnxFib::Add (const CcnxNameComponents &prefix, Ptr<CcnxFace> face, int32_t metric)
-{
- return Add (Create<CcnxNameComponents> (prefix), face, metric);
-}
-
-CcnxFibEntryContainer::type::iterator
-CcnxFib::Add (const Ptr<const CcnxNameComponents> &prefix, Ptr<CcnxFace> face, int32_t metric)
-{
-// CcnxFibFaceMetric
- NS_LOG_FUNCTION(this->GetObject<Node> ()->GetId () << boost::cref(*prefix) << boost::cref(*face) << metric);
- CcnxFibEntryContainer::type::iterator entry = m_fib.find (*prefix);
- if (entry == m_fib.end ())
- {
- entry = m_fib.insert (m_fib.end (), CcnxFibEntry (prefix));
- // insert new
- }
-
- NS_ASSERT_MSG (face != NULL, "Trying to modify NULL face");
- m_fib.modify (entry,
- ll::bind (&CcnxFibEntry::AddOrUpdateRoutingMetric, ll::_1, face, metric));
-
- return entry;
-}
-
-void
-CcnxFib::Remove (const Ptr<const CcnxNameComponents> &prefix)
-{
- NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
- CcnxFibEntryContainer::type::iterator entry = m_fib.find (*prefix);
- if (entry != m_fib.end ())
- m_fib.erase (entry);
-}
-
-void
-CcnxFib::Invalidate (const Ptr<const CcnxNameComponents> &prefix)
-{
- NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
-
- CcnxFibEntryContainer::type::iterator entry = m_fib.find (*prefix);
- if (entry == m_fib.end ())
- return; // nothing to invalidate
-
- m_fib.modify (entry,
- ll::bind (&CcnxFibEntry::Invalidate, ll::_1));
-}
-
-void
-CcnxFib::InvalidateAll ()
-{
- NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId ());
-
- for (CcnxFibEntryContainer::type::iterator entry = m_fib.begin ();
- entry != m_fib.end ();
- entry ++)
- {
- m_fib.modify (entry,
- ll::bind (&CcnxFibEntry::Invalidate, ll::_1));
- }
-}
-
-void
-CcnxFib::Remove (const CcnxFibEntry &entry, Ptr<CcnxFace> face)
-{
- NS_LOG_FUNCTION (this);
-
- m_fib.modify (m_fib.iterator_to (entry),
- ll::bind (&CcnxFibEntry::RemoveFace, ll::_1, face));
- if (entry.m_faces.size () == 0)
- {
- m_fib.erase (m_fib.iterator_to (entry));
- }
-}
-
-void
-CcnxFib::RemoveFromAll (Ptr<CcnxFace> face)
-{
- NS_LOG_FUNCTION (this);
-
- for_each (m_fib.begin (), m_fib.end (),
- ll::bind (static_cast< void (CcnxFib::*) (const CcnxFibEntry &, Ptr<CcnxFace>) > (&CcnxFib::Remove),
- this, ll::_1, face));
-}
-
-
std::ostream& operator<< (std::ostream& os, const CcnxFib &fib)
{
- os << "Node " << Names::FindName (fib.m_node) << "\n";
+ os << "Node " << Names::FindName (fib.GetObject<Node>()) << "\n";
os << " Dest prefix Interfaces(Costs) \n";
os << "+-------------+--------------------------------------+\n";
-
- for (CcnxFibEntryContainer::type::iterator entry = fib.m_fib.begin ();
- entry != fib.m_fib.end ();
- entry++)
- {
- os << entry->GetPrefix () << "\t" << *entry << "\n";
- }
+
+ fib.Print (os);
return os;
}
-std::ostream& operator<< (std::ostream& os, const CcnxFibEntry &entry)
-{
- for (CcnxFibFaceMetricContainer::type::index<i_nth>::type::iterator metric =
- entry.m_faces.get<i_nth> ().begin ();
- metric != entry.m_faces.get<i_nth> ().end ();
- metric++)
- {
- if (metric != entry.m_faces.get<i_nth> ().begin ())
- os << ", ";
-
- os << *metric;
- }
- return os;
-}
-
-std::ostream& operator<< (std::ostream& os, const CcnxFibFaceMetric &metric)
-{
- static const std::string statusString[] = {"","g","y","r"};
-
- os << *metric.m_face << "(" << metric.m_routingCost << ","<< statusString [metric.m_status] << "," << metric.m_face->GetMetric () << ")";
- return os;
-}
-
-// void CcnxFib::resetProbing()
-// {
-// for(FibRangeIterator fib = _fib.begin(); fib != _fib.end(); fib++)
-// VALUE(fib).needsProbing = true;
-// }
-
-// void CcnxFib::updateInterfaceStatus( int interface, int status )
-// {
-// for( FibRangeIterator fib = _fib.begin(); fib!=_fib.end(); fib++ )
-// {
-// VALUE(fib).updateStatus( interface, status );
-// }
-// }
-
} // namespace ns3
diff --git a/model/ccnx-fib.h b/model/ccnx-fib.h
index 1baaf6f..31fd2d8 100644
--- a/model/ccnx-fib.h
+++ b/model/ccnx-fib.h
@@ -21,23 +21,10 @@
#ifndef _CCNX_FIB_H_
#define _CCNX_FIB_H_
-#include "ccnx-name-components-hash-helper.h"
-#include "ccnx-face.h"
-#include "ccnx.h"
-#include "ns3/nstime.h"
#include "ns3/simple-ref-count.h"
#include "ns3/node.h"
-#include <boost/multi_index_container.hpp>
-#include <boost/multi_index/tag.hpp>
-#include <boost/multi_index/ordered_index.hpp>
-#include <boost/multi_index/composite_key.hpp>
-#include <boost/multi_index/hashed_index.hpp>
-#include <boost/multi_index/random_access_index.hpp>
-#include <boost/multi_index/member.hpp>
-#include <boost/multi_index/mem_fun.hpp>
-
-#include <iostream>
+#include "ns3/ccnx-fib-entry.h"
namespace ns3 {
@@ -45,242 +32,24 @@
/**
* \ingroup ccnx
- * \brief Structure holding various parameters associated with a (FibEntry, Face) tuple
- */
-class CcnxFibFaceMetric
-{
-public:
- /**
- * @brief Color codes for FIB face status
- */
- enum Status { NDN_FIB_GREEN = 1,
- NDN_FIB_YELLOW = 2,
- NDN_FIB_RED = 3 };
-public:
- /**
- * \brief Metric constructor
- *
- * \param face Face for which metric
- * \param cost Initial value for routing cost
- */
- CcnxFibFaceMetric (Ptr<CcnxFace> face, int32_t cost)
- : m_face (face)
- , m_status (NDN_FIB_YELLOW)
- , m_routingCost (cost)
- , m_sRtt (Seconds (0))
- , m_rttVar (Seconds (0))
- { }
-
- /**
- * \brief Comparison operator used by boost::multi_index::identity<>
- */
- bool
- operator< (const CcnxFibFaceMetric &fm) const { return *m_face < *fm.m_face; } // return identity of the face
-
- /**
- * @brief Comparison between CcnxFibFaceMetric and CcnxFace
- */
- bool
- operator< (const Ptr<CcnxFace> &face) const { return *m_face < *face; }
-
- /**
- * @brief Return CcnxFace associated with CcnxFibFaceMetric
- */
- Ptr<CcnxFace>
- GetFace () const { return m_face; }
-
- /**
- * \brief Recalculate smoothed RTT and RTT variation
- * \param rttSample RTT sample
- */
- void
- UpdateRtt (const Time &rttSample);
-
-private:
- friend std::ostream& operator<< (std::ostream& os, const CcnxFibFaceMetric &metric);
-public:
- Ptr<CcnxFace> m_face; ///< Face
-
- Status m_status; ///< \brief Status of the next hop:
- ///< - NDN_FIB_GREEN
- ///< - NDN_FIB_YELLOW
- ///< - NDN_FIB_RED
-
- int32_t m_routingCost; ///< \brief routing protocol cost (interpretation of the value depends on the underlying routing protocol)
-
- Time m_sRtt; ///< \brief smoothed round-trip time
- Time m_rttVar; ///< \brief round-trip time variation
-};
-
-/**
- * \ingroup ccnx
- * \brief Typedef for indexed face container of CcnxFibEntry
- *
- * Currently, there are 2 indexes:
- * - by face (used to find record and update metric)
- * - by metric (face ranking)
- * - random access index (for fast lookup on nth face). Order is
- * maintained manually to be equal to the 'by metric' order
- */
-struct CcnxFibFaceMetricContainer
-{
- /// @cond include_hidden
- typedef boost::multi_index::multi_index_container<
- CcnxFibFaceMetric,
- boost::multi_index::indexed_by<
- // For fast access to elements using CcnxFace
- boost::multi_index::ordered_unique<
- boost::multi_index::tag<__ccnx_private::i_face>,
- boost::multi_index::member<CcnxFibFaceMetric,Ptr<CcnxFace>,&CcnxFibFaceMetric::m_face>
- >,
-
- // List of available faces ordered by (status, m_routingCost)
- boost::multi_index::ordered_non_unique<
- boost::multi_index::tag<__ccnx_private::i_metric>,
- boost::multi_index::composite_key<
- CcnxFibFaceMetric,
- boost::multi_index::member<CcnxFibFaceMetric,CcnxFibFaceMetric::Status,&CcnxFibFaceMetric::m_status>,
- boost::multi_index::member<CcnxFibFaceMetric,int32_t,&CcnxFibFaceMetric::m_routingCost>
- >
- >,
-
- // To optimize nth candidate selection (sacrifice a little bit space to gain speed)
- boost::multi_index::random_access<
- boost::multi_index::tag<__ccnx_private::i_nth>
- >
- >
- > type;
- /// @endcond
-};
-
-/**
- * \ingroup ccnx
- * \brief Structure for FIB table entry, holding indexed list of
- * available faces and their respective metrics
- */
-class CcnxFibEntry // : public SimpleRefCount<CcnxFibEntry>
-{
-public:
- class NoFaces {}; ///< @brief Exception class for the case when FIB entry is not found
-
- /**
- * \brief Constructor
- * \param prefix smart pointer to the prefix for the FIB entry
- */
- CcnxFibEntry (const Ptr<const CcnxNameComponents> &prefix)
- : m_prefix (prefix)
- , m_needsProbing (false)
- { }
-
- /**
- * \brief Update status of FIB next hop
- * \param status Status to set on the FIB entry
- */
- void UpdateStatus (Ptr<CcnxFace> face, CcnxFibFaceMetric::Status status);
-
- /**
- * \brief Add or update routing metric of FIB next hop
- *
- * Initial status of the next hop is set to YELLOW
- */
- void AddOrUpdateRoutingMetric (Ptr<CcnxFace> face, int32_t metric);
-
- /**
- * @brief Invalidate face
- *
- * Set routing metric on all faces to max and status to RED
- */
- void
- Invalidate ();
-
- /**
- * @brief Update RTT averages for the face
- */
- void
- UpdateFaceRtt (Ptr<CcnxFace> face, const Time &sample);
-
- /**
- * \brief Get prefix for the FIB entry
- */
- const CcnxNameComponents&
- GetPrefix () const { return *m_prefix; }
-
- /**
- * \brief Find "best route" candidate, skipping `skip' first candidates (modulo # of faces)
- *
- * throws CcnxFibEntry::NoFaces if m_faces.size()==0
- */
- const CcnxFibFaceMetric &
- FindBestCandidate (uint32_t skip = 0) const;
-
- /**
- * @brief Remove record associated with `face`
- */
- void
- RemoveFace (const Ptr<CcnxFace> &face)
- {
- m_faces.erase (face);
- }
-
-private:
- friend std::ostream& operator<< (std::ostream& os, const CcnxFibEntry &entry);
-
-public:
- Ptr<const CcnxNameComponents> m_prefix; ///< \brief Prefix of the FIB entry
- CcnxFibFaceMetricContainer::type m_faces; ///< \brief Indexed list of faces
-
- bool m_needsProbing; ///< \brief flag indicating that probing should be performed
-};
-
-///////////////////////////////////////////////////////////////////////////////
-///////////////////////////////////////////////////////////////////////////////
-
-/**
- * \ingroup ccnx
- * \brief Typedef for indexed container for FIB entries
- *
- * Currently, there is only one index
- * - by prefix hash, which is used to perform prefix match
- */
-struct CcnxFibEntryContainer
-{
- /// @cond include_hidden
- typedef boost::multi_index::multi_index_container<
- CcnxFibEntry,
- boost::multi_index::indexed_by<
- // For fast access to elements using CcnxFace
- boost::multi_index::hashed_unique<
- boost::multi_index::tag<__ccnx_private::i_prefix>,
- boost::multi_index::const_mem_fun<CcnxFibEntry,
- const CcnxNameComponents&,
- &CcnxFibEntry::GetPrefix>,
- CcnxPrefixHash>
- >
- > type;
- /// @endcond
-};
-
-/**
- * \ingroup ccnx
* \brief Class implementing FIB functionality
*/
class CcnxFib : public Object
{
public:
- typedef CcnxFibEntryContainer::type::iterator iterator;
+ typedef ns3::Ptr<CcnxFibEntry> iterator; // not sure, but let's see what will happen
+ typedef ns3::Ptr<CcnxFibEntry> const_iterator;
+
+ /**
+ * @brief Default constructor
+ */
+ CcnxFib () {}
/**
- * \brief Interface ID
- *
- * \return interface ID
+ * @brief Virtual destructor
*/
- static TypeId GetTypeId ();
-
- /**
- * \brief Constructor
- */
- CcnxFib ();
-
+ virtual ~CcnxFib () { };
+
/**
* \brief Perform longest prefix match
*
@@ -289,8 +58,8 @@
* \param interest Interest packet header
* \returns If entry found a valid iterator will be returned, otherwise end ()
*/
- CcnxFibEntryContainer::type::iterator
- LongestPrefixMatch (const CcnxInterestHeader &interest) const;
+ virtual iterator
+ LongestPrefixMatch (const CcnxInterestHeader &interest) const = 0;
/**
* \brief Add or update FIB entry
@@ -303,8 +72,8 @@
* @param face Forwarding face
* @param metric Routing metric
*/
- CcnxFibEntryContainer::type::iterator
- Add (const CcnxNameComponents &prefix, Ptr<CcnxFace> face, int32_t metric);
+ virtual iterator
+ Add (const CcnxNameComponents &prefix, Ptr<CcnxFace> face, int32_t metric) = 0;
/**
* \brief Add or update FIB entry using smart pointer to prefix
@@ -317,8 +86,8 @@
* @param face Forwarding face
* @param metric Routing metric
*/
- CcnxFibEntryContainer::type::iterator
- Add (const Ptr<const CcnxNameComponents> &prefix, Ptr<CcnxFace> face, int32_t metric);
+ virtual iterator
+ Add (const Ptr<const CcnxNameComponents> &prefix, Ptr<CcnxFace> face, int32_t metric) = 0;
/**
* @brief Remove FIB entry
@@ -328,8 +97,8 @@
*
* @param name Smart pointer to prefix
*/
- void
- Remove (const Ptr<const CcnxNameComponents> &prefix);
+ virtual void
+ Remove (const Ptr<const CcnxNameComponents> &prefix) = 0;
/**
* @brief Invalidate FIB entry ("Safe" version of Remove)
@@ -337,51 +106,54 @@
* All faces for the entry will be assigned maximum routing metric and NDN_FIB_RED status
* @param name Smart pointer to prefix
*/
- void
- Invalidate (const Ptr<const CcnxNameComponents> &prefix);
+ virtual void
+ Invalidate (const Ptr<const CcnxNameComponents> &prefix) = 0;
/**
* @brief Invalidate all FIB entries
*/
- void
- InvalidateAll ();
+ virtual void
+ InvalidateAll () = 0;
/**
* @brief Remove reference to a face from the entry. If entry had only this face, the whole
* entry will be removed
*/
- void
- Remove (const CcnxFibEntry &entry, Ptr<CcnxFace> face);
+ virtual void
+ Remove (const CcnxFibEntry &entry, Ptr<CcnxFace> face) = 0;
/**
* @brief Remove all references to a face from FIB. If for some enty that face was the only element,
* this FIB entry will be removed.
*/
- void
- RemoveFromAll (Ptr<CcnxFace> face);
+ virtual void
+ RemoveFromAll (Ptr<CcnxFace> face) = 0;
-public:
- CcnxFibEntryContainer::type m_fib; ///< @brief Internal container
-
-protected:
- // inherited from Object class
- virtual void NotifyNewAggregate (); ///< @brief Notify when object is aggregated
- virtual void DoDispose (); ///< @brief Perform cleanup
+ /**
+ * @brief Print out entries in FIB
+ */
+ virtual void
+ Print (std::ostream &os) const = 0;
+
+ // /**
+ // * @brief Modify element in container
+ // */
+ // template<typename Modifier>
+ // virtual bool
+ // modify (iterator position, Modifier mod) = 0;
+ // // {
+ // // return this->m_fib.modify (position, mod);
+ // // }
private:
friend std::ostream& operator<< (std::ostream& os, const CcnxFib &fib);
CcnxFib(const CcnxFib&) {} ; ///< \brief copy constructor is disabled
-
-private:
- Ptr<Node> m_node;
};
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
std::ostream& operator<< (std::ostream& os, const CcnxFib &fib);
-std::ostream& operator<< (std::ostream& os, const CcnxFibEntry &entry);
-std::ostream& operator<< (std::ostream& os, const CcnxFibFaceMetric &metric);
} // namespace ns3
diff --git a/model/ccnx-l3-protocol.cc b/model/ccnx-l3-protocol.cc
index 9abe297..72273d5 100644
--- a/model/ccnx-l3-protocol.cc
+++ b/model/ccnx-l3-protocol.cc
@@ -40,6 +40,7 @@
#include "ccnx-forwarding-strategy.h"
#include "ccnx-interest-header.h"
#include "ccnx-content-object-header.h"
+#include "ccnx-fib-impl.h"
#include "ccnx-net-device-face.h"
@@ -333,9 +334,9 @@
ll::bind (&CcnxPitEntry::RemoveIncoming, ll::_1, incomingFace));
}
- m_fib->m_fib.modify (pitEntry->m_fibEntry,
- ll::bind (&CcnxFibEntry::UpdateStatus,
- ll::_1, incomingFace, CcnxFibFaceMetric::NDN_FIB_YELLOW));
+ StaticCast<CcnxFibImpl> (m_fib)->modify (pitEntry->m_fibEntry,
+ ll::bind (&CcnxFibEntry::UpdateStatus,
+ ll::_1, incomingFace, CcnxFibFaceMetric::NDN_FIB_YELLOW));
if (pitEntry->m_incoming.size () == 0) // interest was actually satisfied
{
@@ -484,9 +485,9 @@
// ?? not sure if we need to do that ?? ...
- m_fib->m_fib.modify(pitEntry->m_fibEntry,
- ll::bind (&CcnxFibEntry::UpdateStatus,
- ll::_1, incomingFace, CcnxFibFaceMetric::NDN_FIB_YELLOW));
+ StaticCast<CcnxFibImpl> (m_fib)->modify(pitEntry->m_fibEntry,
+ ll::bind (&CcnxFibEntry::UpdateStatus,
+ ll::_1, incomingFace, CcnxFibFaceMetric::NDN_FIB_YELLOW));
}
else
if (!isNew && !isRetransmitted)
@@ -588,11 +589,11 @@
// If we have sent interest for this data via this face, then update stats.
if (out != pitEntry->m_outgoing.end ())
{
- m_fib->m_fib.modify (pitEntry->m_fibEntry,
- ll::bind (&CcnxFibEntry::UpdateFaceRtt,
- ll::_1,
- incomingFace,
- Simulator::Now () - out->m_sendTime));
+ StaticCast<CcnxFibImpl> (m_fib)->modify (pitEntry->m_fibEntry,
+ ll::bind (&CcnxFibEntry::UpdateFaceRtt,
+ ll::_1,
+ incomingFace,
+ Simulator::Now () - out->m_sendTime));
}
else
{
@@ -615,9 +616,9 @@
}
// Update metric status for the incoming interface in the corresponding FIB entry
- m_fib->m_fib.modify (pitEntry->m_fibEntry,
- ll::bind (&CcnxFibEntry::UpdateStatus, ll::_1,
- incomingFace, CcnxFibFaceMetric::NDN_FIB_GREEN));
+ StaticCast<CcnxFibImpl>(m_fib)->modify (pitEntry->m_fibEntry,
+ ll::bind (&CcnxFibEntry::UpdateStatus, ll::_1,
+ incomingFace, CcnxFibFaceMetric::NDN_FIB_GREEN));
// Add or update entry in the content store
m_contentStore->Add (header, payload);
diff --git a/model/ccnx-pit-entry.cc b/model/ccnx-pit-entry.cc
index 127b589..8375cf9 100644
--- a/model/ccnx-pit-entry.cc
+++ b/model/ccnx-pit-entry.cc
@@ -27,6 +27,7 @@
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
+#include <boost/foreach.hpp>
namespace ll = boost::lambda;
NS_LOG_COMPONENT_DEFINE ("CcnxPitEntry");
diff --git a/utils/detail/multi-policy-container.h b/utils/detail/multi-policy-container.h
index 9fcc061..0fa07b3 100644
--- a/utils/detail/multi-policy-container.h
+++ b/utils/detail/multi-policy-container.h
@@ -77,6 +77,13 @@
Value::value_.erase (item);
Super::erase (item);
}
+
+ void
+ clear ()
+ {
+ Value::value_.clear ();
+ Super::clear ();
+ }
};
template< class Base >
@@ -88,6 +95,7 @@
bool insert (typename Base::iterator item) { return true; }
void lookup (typename Base::iterator item) {}
void erase (typename Base::iterator item) {}
+ void clear () {}
};
template< class Base, class Vector >
diff --git a/utils/empty-policy.h b/utils/empty-policy.h
index 0fe43f8..c5f324c 100644
--- a/utils/empty-policy.h
+++ b/utils/empty-policy.h
@@ -26,21 +26,24 @@
struct empty_policy_traits
{
- typedef void policy_hook_type;
+ typedef void* policy_hook_type;
- template<class Container> struct container_hook { typedef void type; }
+ template<class Container> struct container_hook { typedef void* type; };
template<class Base,
class Container,
class Hook>
struct policy
{
- class type
+ struct type
{
- inline void update (typename parent_trie::iterator) { }
- inline bool insert (typename parent_trie::iterator) { return true; }
- inline void lookup (typename parent_trie::iterator item) { }
- inline void erase (typename parent_trie::iterator item) { }
+ inline type (Base &base) {}
+
+ inline void update (typename Container::iterator) { }
+ inline bool insert (typename Container::iterator) { return true; }
+ inline void lookup (typename Container::iterator item) { }
+ inline void erase (typename Container::iterator item) { }
+ inline void clear () { }
};
};
};
diff --git a/utils/fifo-policy.h b/utils/fifo-policy.h
index 9f215fc..2dccbe4 100644
--- a/utils/fifo-policy.h
+++ b/utils/fifo-policy.h
@@ -90,6 +90,12 @@
}
inline void
+ clear ()
+ {
+ policy_container::clear ();
+ }
+
+ inline void
set_max_size (size_t max_size)
{
max_size_ = max_size;
diff --git a/utils/lru-policy.h b/utils/lru-policy.h
index bf03fa8..077d602 100644
--- a/utils/lru-policy.h
+++ b/utils/lru-policy.h
@@ -95,6 +95,12 @@
}
inline void
+ clear ()
+ {
+ policy_container::clear ();
+ }
+
+ inline void
set_max_size (size_t max_size)
{
max_size_ = max_size;
diff --git a/utils/multi-policy.h b/utils/multi-policy.h
index fd126ae..f5cf682 100644
--- a/utils/multi-policy.h
+++ b/utils/multi-policy.h
@@ -115,6 +115,12 @@
{
policy_container::erase (item);
}
+
+ inline void
+ clear ()
+ {
+ policy_container::clear ();
+ }
};
};
};
diff --git a/utils/random-policy.h b/utils/random-policy.h
index 705bcf3..7a96712 100644
--- a/utils/random-policy.h
+++ b/utils/random-policy.h
@@ -127,6 +127,12 @@
}
inline void
+ clear ()
+ {
+ policy_container::clear ();
+ }
+
+ inline void
set_max_size (size_t max_size)
{
max_size_ = max_size;
diff --git a/utils/trie-with-policy.h b/utils/trie-with-policy.h
index c674ef2..79480da 100644
--- a/utils/trie-with-policy.h
+++ b/utils/trie-with-policy.h
@@ -53,7 +53,7 @@
}
inline std::pair< iterator, bool >
- insert (const FullKey &key, typename PayloadTraits::const_pointer_type payload)
+ insert (const FullKey &key, typename PayloadTraits::pointer_type payload)
{
std::pair<iterator, bool> item =
trie_.insert (key, payload);
@@ -69,14 +69,26 @@
}
else
{
- item.first->set_payload (payload);
- policy_.update (s_iterator_to (item.first));
+ return std::make_pair (s_iterator_to (item.first), false);
}
return item;
}
inline void
+ erase (const FullKey &key)
+ {
+ iterator foundItem, lastItem;
+ bool reachLast;
+ boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+
+ if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
+ return; // nothing to invalidate
+
+ erase (lastItem);
+ }
+
+ inline void
erase (iterator node)
{
if (node == end ()) return;
@@ -85,18 +97,39 @@
node->erase (); // will do cleanup here
}
+ inline void
+ clear ()
+ {
+ policy_.clear ();
+ trie_.clear ();
+ }
+
+ template<typename Modifier>
+ bool
+ modify (iterator position, Modifier mod)
+ {
+ if (position == end ()) return false;
+ if (position->payload () == PayloadTraits::empty_payload) return false;
+
+ mod (*position->payload ());
+ policy_.update (position);
+ return true;
+ }
+
/**
* @brief Find a node that has the longest common prefix with key (FIB/PIT lookup)
*/
inline iterator
longest_prefix_match (const FullKey &key)
{
- boost::tuple< iterator, bool, iterator > item = trie_.find (key);
- if (item.template get<0> () != trie_.end ())
+ iterator foundItem, lastItem;
+ bool reachLast;
+ boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+ if (foundItem != trie_.end ())
{
- policy_.lookup (s_iterator_to (item.template get<0> ()));
+ policy_.lookup (s_iterator_to (foundItem));
}
- return item.template get<0> ();
+ return foundItem;
}
/**
@@ -159,7 +192,7 @@
}
}
- iterator end ()
+ iterator end () const
{
return 0;
}
@@ -190,4 +223,3 @@
} // ndnSIM
#endif // TRIE_WITH_POLICY_H_
-
diff --git a/utils/trie.h b/utils/trie.h
index 47e62e5..86ca01f 100644
--- a/utils/trie.h
+++ b/utils/trie.h
@@ -29,6 +29,7 @@
#include <boost/functional/hash.hpp>
#include <boost/interprocess/smart_ptr/unique_ptr.hpp>
#include <boost/tuple/tuple.hpp>
+#include <boost/foreach.hpp>
namespace ndnSIM
{
@@ -43,11 +44,11 @@
typedef Payload* pointer_type;
typedef const Payload* const_pointer_type;
- static const Payload* empty_payload;
+ static Payload* empty_payload;
};
template<typename Payload>
-const Payload*
+Payload*
pointer_payload_traits<Payload>::empty_payload = 0;
template<typename Payload>
@@ -57,11 +58,11 @@
typedef ns3::Ptr<Payload> pointer_type;
typedef ns3::Ptr<const Payload> const_pointer_type;
- static const ns3::Ptr<const Payload> empty_payload;
+ static ns3::Ptr<Payload> empty_payload;
};
template<typename Payload>
-const ns3::Ptr<const Payload>
+ns3::Ptr<Payload>
smart_pointer_payload_traits<Payload>::empty_payload = 0;
@@ -109,6 +110,12 @@
inline
~trie ();
+
+ void
+ clear ()
+ {
+ children_.clear_and_dispose (trie_delete_disposer ());
+ }
// actual entry
friend bool
@@ -120,7 +127,7 @@
inline std::pair<iterator, bool>
insert (const FullKey &key,
- typename PayloadTraits::const_pointer_type payload);
+ typename PayloadTraits::pointer_type payload);
/**
* @brief Removes payload (if it exists) and if there are no children, prunes parents trie
@@ -134,6 +141,12 @@
inline void
prune ();
+ inline boost::tuple<const iterator, bool, const iterator>
+ find (const FullKey &key) const
+ {
+ return const_cast<trie*> (this)->find (key);
+ }
+
/**
* @brief Perform the longest prefix match
* @param key the key for which to perform the longest prefix match
@@ -175,8 +188,14 @@
return payload_;
}
+ typename PayloadTraits::pointer_type
+ payload ()
+ {
+ return payload_;
+ }
+
void
- set_payload (typename PayloadTraits::const_pointer_type payload)
+ set_payload (typename PayloadTraits::pointer_type payload)
{
payload_ = payload;
}
@@ -237,7 +256,7 @@
buckets_array buckets_;
unordered_set children_;
- typename PayloadTraits::const_pointer_type payload_;
+ typename PayloadTraits::pointer_type payload_;
trie *parent_; // to make cleaning effective
};
@@ -267,7 +286,7 @@
inline
std::pair<typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator, bool>
trie<FullKey, Payload, PayloadTraits, PolicyHook>
-::insert (const FullKey &key, typename PayloadTraits::const_pointer_type payload)
+::insert (const FullKey &key, typename PayloadTraits::pointer_type payload)
{
trie *trieNode = this;
diff --git a/wscript b/wscript
index 07dbcc7..2fb7153 100644
--- a/wscript
+++ b/wscript
@@ -88,6 +88,7 @@
"model/ccnx-pit-entry-outgoing-face.h",
"model/ccnx-content-store.h",
"model/ccnx-fib.h",
+ "model/ccnx-fib-entry.h",
"model/ccnx-face.h",
"model/ccnx-app-face.h",
"model/ccnx-net-device-face.h",