model: (Re-)Implementing ability to keep PIT records after Interest is getting satisfied
Default behavior remained the same.
As part of this commit, a small extension (and bug fix) in trie data
structure, allowing search with predicates (e.g., used to lookup a
non-empty PIT entry during Lookup on ContentObject header).
diff --git a/model/pit/ndn-pit-entry.cc b/model/pit/ndn-pit-entry.cc
index 77c7578..accfcf1 100644
--- a/model/pit/ndn-pit-entry.cc
+++ b/model/pit/ndn-pit-entry.cc
@@ -62,12 +62,12 @@
Entry::UpdateLifetime (const Time &offsetTime)
{
NS_LOG_FUNCTION (offsetTime.ToDouble (Time::S));
-
+
Time newExpireTime = Simulator::Now () + offsetTime;
if (newExpireTime > m_expireTime)
m_expireTime = newExpireTime;
-
- NS_LOG_INFO ("Updated lifetime to " << m_expireTime.ToDouble (Time::S));
+
+ NS_LOG_INFO (this->GetPrefix () << ", Updated lifetime to " << m_expireTime.ToDouble (Time::S) << "s, " << (m_expireTime-Simulator::Now ()).ToDouble (Time::S) << "s left");
}
void
@@ -78,7 +78,7 @@
{
m_expireTime = Simulator::Now ();
}
- NS_LOG_INFO ("Offsetting lifetime to " << m_expireTime.ToDouble (Time::S));
+ NS_LOG_INFO (this->GetPrefix () << ", Offsetting lifetime to " << m_expireTime.ToDouble (Time::S) << "s, " << (m_expireTime-Simulator::Now ()).ToDouble (Time::S) << "s left");
}
@@ -110,7 +110,7 @@
Entry::in_iterator
Entry::AddIncoming (Ptr<Face> face)
{
- std::pair<in_iterator,bool> ret =
+ std::pair<in_iterator,bool> ret =
m_incoming.insert (IncomingFace (face));
// NS_ASSERT_MSG (ret.second, "Something is wrong");
@@ -277,7 +277,7 @@
os << ",";
else
first = false;
-
+
os << *face.m_face;
}
@@ -289,7 +289,7 @@
os << ",";
else
first = false;
-
+
os << *face.m_face;
}
os << "\nNonces: ";
@@ -300,7 +300,7 @@
os << ",";
else
first = false;
-
+
os << nonce;
}
diff --git a/model/pit/ndn-pit-entry.h b/model/pit/ndn-pit-entry.h
index 259af75..9680ac2 100644
--- a/model/pit/ndn-pit-entry.h
+++ b/model/pit/ndn-pit-entry.h
@@ -75,7 +75,7 @@
// // boost::multi_index::ordered_non_unique<
// // boost::multi_index::tag<i_retx>,
// // boost::multi_index::member<OutgoingFace, uint32_t, &OutgoingFace::m_retxCount>
-// // >
+// // >
// >
// > type;
// /// @endcond
@@ -99,7 +99,7 @@
typedef out_container::iterator out_iterator; ///< @brief iterator to outgoing faces
typedef std::set< uint32_t > nonce_container; ///< @brief nonce container type
-
+
/**
* \brief PIT entry constructor
* \param prefix Prefix of the PIT entry
@@ -112,33 +112,34 @@
* @brief Virtual destructor
*/
virtual ~Entry ();
-
+
/**
* @brief Update lifetime of PIT entry
*
- * This function will update PIT entry lifetime to the maximum of the current lifetime and
- * the lifetime Simulator::Now () + offsetTime
+ * @param lifetime desired lifetime of the pit entry (relative to the Simulator::Now ())
*
- * @param lifetime Relative time to the current moment, representing PIT entry lifetime
+ * This function will update PIT entry lifetime to the maximum of the current lifetime and
+ * the lifetime Simulator::Now () + lifetime
*/
virtual void
UpdateLifetime (const Time &lifetime);
/**
* @brief Offset the currently set PIT lifetime (allowed both negative and positive offsets)
+ *
* @param offsetTime positive or negative offset for the PIT lifetime.
*
* If PIT expire time becomes less than Simulator::Now, then it is adjusted to Simulator::Now.
*/
virtual void
OffsetLifetime (const Time &offsetTime);
-
+
/**
* @brief Get prefix of the PIT entry
*/
const NameComponents &
GetPrefix () const;
-
+
/**
* @brief Get current expiration time of the record
*
@@ -146,7 +147,7 @@
*/
const Time &
GetExpireTime () const;
-
+
/**
* @brief Check if nonce `nonce` for the same prefix has already been seen
*
@@ -154,7 +155,7 @@
*/
bool
IsNonceSeen (uint32_t nonce) const;
-
+
/**
* @brief Add `nonce` to the list of seen nonces
*
@@ -164,7 +165,7 @@
*/
virtual void
AddSeenNonce (uint32_t nonce);
-
+
/**
* @brief Add `face` to the list of incoming faces
*
@@ -200,10 +201,10 @@
*/
virtual void
ClearOutgoing ();
-
+
/**
* @brief Remove all references to face.
- *
+ *
* This method should be called before face is completely removed from the stack.
* Face is removed from the lists of incoming and outgoing faces
*/
@@ -217,7 +218,7 @@
// SetWaitingInVain (out_iterator face);
virtual void
SetWaitingInVain (Ptr<Face> face);
-
+
/**
* @brief Check if all outgoing faces are NACKed
*/
@@ -266,7 +267,7 @@
*/
uint32_t
GetOutgoingCount () const;
-
+
/**
* @brief Add new forwarding strategy tag
*/
@@ -295,14 +296,14 @@
private:
friend std::ostream& operator<< (std::ostream& os, const Entry &entry);
-
+
protected:
Pit &m_container; ///< @brief Reference to the container (to rearrange indexes, if necessary)
Ptr<const InterestHeader> m_interest; ///< \brief Interest of the PIT entry (if several interests are received, then nonce is from the first Interest)
Ptr<fib::Entry> m_fibEntry; ///< \brief FIB entry related to this prefix
-
- nonce_container m_seenNonces; ///< \brief map of nonces that were seen for this prefix
+
+ nonce_container m_seenNonces; ///< \brief map of nonces that were seen for this prefix
in_container m_incoming; ///< \brief container for incoming interests
out_container m_outgoing; ///< \brief container for outgoing interests
@@ -314,6 +315,15 @@
std::list< boost::shared_ptr<fw::Tag> > m_fwTags; ///< @brief Forwarding strategy tags
};
+struct EntryIsNotEmpty
+{
+ bool
+ operator () (Ptr<Entry> entry)
+ {
+ return !entry->GetIncoming ().empty ();
+ }
+};
+
std::ostream& operator<< (std::ostream& os, const Entry &entry);
inline void
diff --git a/model/pit/ndn-pit-impl.cc b/model/pit/ndn-pit-impl.cc
index 3b693f8..27fcab2 100644
--- a/model/pit/ndn-pit-impl.cc
+++ b/model/pit/ndn-pit-impl.cc
@@ -185,7 +185,7 @@
PitImpl<Policy>::Lookup (const ContentObjectHeader &header)
{
/// @todo use predicate to search with exclude filters
- typename super::iterator item = super::longest_prefix_match (header.GetName ());
+ typename super::iterator item = super::longest_prefix_match_if (header.GetName (), EntryIsNotEmpty ());
if (item == super::end ())
return 0;
@@ -249,8 +249,14 @@
void
PitImpl<Policy>::MarkErased (Ptr<Entry> item)
{
- // entry->SetExpireTime (Simulator::Now () + m_PitEntryPruningTimout);
- super::erase (StaticCast< entry > (item)->to_iterator ());
+ if (this->m_PitEntryPruningTimout.IsZero ())
+ {
+ super::erase (StaticCast< entry > (item)->to_iterator ());
+ }
+ else
+ {
+ item->OffsetLifetime (this->m_PitEntryPruningTimout - item->GetExpireTime () + Simulator::Now ());
+ }
}
diff --git a/model/pit/ndn-pit.cc b/model/pit/ndn-pit.cc
index ad8f4a2..224e013 100644
--- a/model/pit/ndn-pit.cc
+++ b/model/pit/ndn-pit.cc
@@ -24,7 +24,7 @@
#include "ns3/ndn-content-object.h"
#include "ns3/log.h"
-#include "ns3/string.h"
+#include "ns3/nstime.h"
#include "ns3/uinteger.h"
#include "ns3/simulator.h"
@@ -44,10 +44,10 @@
static TypeId tid = TypeId ("ns3::ndn::Pit")
.SetGroupName ("Ndn")
.SetParent<Object> ()
-
+
.AddAttribute ("PitEntryPruningTimout",
"Timeout for PIT entry to live after being satisfied. To make sure recently satisfied interest will not be satisfied again",
- StringValue ("100ms"),
+ TimeValue (), // by default, PIT entries are removed instantly
MakeTimeAccessor (&Pit::m_PitEntryPruningTimout),
MakeTimeChecker ())
;
diff --git a/utils/trie/trie-with-policy.h b/utils/trie/trie-with-policy.h
index 08cb21c..2d175a0 100644
--- a/utils/trie/trie-with-policy.h
+++ b/utils/trie/trie-with-policy.h
@@ -82,7 +82,7 @@
iterator foundItem, lastItem;
bool reachLast;
boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
-
+
if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
return; // nothing to invalidate
@@ -126,13 +126,13 @@
iterator foundItem, lastItem;
bool reachLast;
boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
-
+
if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
return end ();
return lastItem;
}
-
+
/**
* @brief Find a node that has the longest common prefix with key (FIB/PIT lookup)
*/
@@ -149,6 +149,23 @@
return foundItem;
}
+ /**
+ * @brief Find a node that has the longest common prefix with key (FIB/PIT lookup)
+ */
+ template<class Predicate>
+ inline iterator
+ longest_prefix_match_if (const FullKey &key, Predicate pred)
+ {
+ iterator foundItem, lastItem;
+ bool reachLast;
+ boost::tie (foundItem, reachLast, lastItem) = trie_.find_if (key, pred);
+ if (foundItem != trie_.end ())
+ {
+ policy_.lookup (s_iterator_to (foundItem));
+ }
+ return foundItem;
+ }
+
// /**
// * @brief Const version of the longest common prefix match
// * (semi-const, because there could be update of the policy anyways)
@@ -172,7 +189,7 @@
// guard in case we don't have anything in the trie
if (lastItem == trie_.end ())
return trie_.end ();
-
+
if (reachLast)
{
if (foundItem == trie_.end ())
@@ -202,7 +219,7 @@
// guard in case we don't have anything in the trie
if (lastItem == trie_.end ())
return trie_.end ();
-
+
if (reachLast)
{
foundItem = lastItem->find_if (pred); // may or may not find something
@@ -244,7 +261,7 @@
else
return &(*item);
}
-
+
private:
parent_trie trie_;
mutable policy_container policy_;
diff --git a/utils/trie/trie.h b/utils/trie/trie.h
index b890631..62411d6 100644
--- a/utils/trie/trie.h
+++ b/utils/trie/trie.h
@@ -51,7 +51,7 @@
typedef BasePayload* base_type; // base type of the entry (when implementation details need to be hidden)
typedef const BasePayload* const_base_type; // const base type of the entry (when implementation details need to be hidden)
-
+
static Payload* empty_payload;
};
@@ -65,13 +65,13 @@
typedef Payload payload_type;
typedef ns3::Ptr<Payload> storage_type;
typedef ns3::Ptr<Payload> insert_type;
-
+
typedef ns3::Ptr<Payload> return_type;
typedef ns3::Ptr<const Payload> const_return_type;
typedef ns3::Ptr<BasePayload> base_type;
typedef ns3::Ptr<const BasePayload> const_base_type;
-
+
static ns3::Ptr<Payload> empty_payload;
};
@@ -88,15 +88,15 @@
typedef Payload& return_type;
typedef const Payload & const_return_type;
-
+
typedef BasePayload& base_type;
typedef const BasePayload& const_base_type;
-
+
static Payload empty_payload;
};
template<typename Payload, typename BasePayload>
-Payload
+Payload
non_pointer_traits<Payload, BasePayload>::empty_payload = Payload ();
@@ -106,7 +106,7 @@
template<typename FullKey,
typename PayloadTraits,
typename PolicyHook >
-class trie;
+class trie;
template<typename FullKey, typename PayloadTraits, typename PolicyHook>
inline std::ostream&
@@ -149,7 +149,7 @@
typedef trie_point_iterator<const trie> const_point_iterator;
typedef PayloadTraits payload_traits;
-
+
inline
trie (const Key &key, size_t bucketSize = 10, size_t bucketIncrement = 10)
: key_ (key)
@@ -192,7 +192,7 @@
trieNode ++;
}
}
-
+
// actual entry
friend bool
operator== <> (const trie<FullKey, PayloadTraits, PolicyHook> &a,
@@ -206,7 +206,7 @@
typename PayloadTraits::insert_type payload)
{
trie *trieNode = this;
-
+
BOOST_FOREACH (const Key &subkey, key)
{
typename unordered_set::iterator item = trieNode->children_.find (subkey);
@@ -220,15 +220,15 @@
{
trieNode->bucketSize_ += trieNode->bucketIncrement_;
trieNode->bucketIncrement_ *= 2; // increase bucketIncrement exponentially
-
+
buckets_array newBuckets (new bucket_type [trieNode->bucketSize_]);
trieNode->children_.rehash (bucket_traits (newBuckets.get (), trieNode->bucketSize_));
trieNode->buckets_.swap (newBuckets);
}
-
+
std::pair< typename unordered_set::iterator, bool > ret =
trieNode->children_.insert (*newNode);
-
+
trieNode = &(*ret.first);
}
else
@@ -307,7 +307,7 @@
trie *trieNode = this;
iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
bool reachLast = true;
-
+
BOOST_FOREACH (const Key &subkey, key)
{
typename unordered_set::iterator item = trieNode->children_.find (subkey);
@@ -319,13 +319,50 @@
else
{
trieNode = &(*item);
-
+
if (trieNode->payload_ != PayloadTraits::empty_payload)
foundNode = trieNode;
}
}
- return boost::make_tuple (foundNode, reachLast, trieNode);
+ return boost::make_tuple (foundNode, reachLast, trieNode);
+ }
+
+ /**
+ * @brief Perform the longest prefix match satisfying preficate
+ * @param key the key for which to perform the longest prefix match
+ *
+ * @return ->second is true if prefix in ->first is longer than key
+ */
+ template<class Predicate>
+ inline boost::tuple<iterator, bool, iterator>
+ find_if (const FullKey &key, Predicate pred)
+ {
+ trie *trieNode = this;
+ iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
+ bool reachLast = true;
+
+ BOOST_FOREACH (const Key &subkey, key)
+ {
+ typename unordered_set::iterator item = trieNode->children_.find (subkey);
+ if (item == trieNode->children_.end ())
+ {
+ reachLast = false;
+ break;
+ }
+ else
+ {
+ trieNode = &(*item);
+
+ if (trieNode->payload_ != PayloadTraits::empty_payload &&
+ pred (trieNode->payload_))
+ {
+ foundNode = trieNode;
+ }
+ }
+ }
+
+ return boost::make_tuple (foundNode, reachLast, trieNode);
}
/**
@@ -348,7 +385,7 @@
if (value != 0)
return value;
}
-
+
return 0;
}
@@ -370,11 +407,11 @@
subnode++ )
// BOOST_FOREACH (const trie &subnode, children_)
{
- iterator value = subnode->find ();
+ iterator value = subnode->find_if (pred);
if (value != 0)
return value;
}
-
+
return 0;
}
@@ -410,10 +447,10 @@
{
return key_;
}
-
+
inline void
- PrintStat (std::ostream &os) const;
-
+ PrintStat (std::ostream &os) const;
+
private:
//The disposer object function
struct trie_delete_disposer
@@ -462,7 +499,7 @@
////////////////////////////////////////////////
// Actual data
////////////////////////////////////////////////
-
+
Key key_; ///< name component
size_t initialBucketSize_;
@@ -472,7 +509,7 @@
typedef boost::interprocess::unique_ptr< bucket_type, array_disposer<bucket_type> > buckets_array;
buckets_array buckets_;
unordered_set children_;
-
+
typename PayloadTraits::storage_type payload_;
trie *parent_; // to make cleaning effective
};
@@ -494,7 +531,7 @@
{
os << "\"" << &trie_node << "\"" << " [label=\"" << trie_node.key_ << ((trie_node.payload_ != PayloadTraits::empty_payload)?"*":"") << "\"]\n";
os << "\"" << &(*subnode) << "\"" << " [label=\"" << subnode->key_ << ((subnode->payload_ != PayloadTraits::empty_payload)?"*":"") << "\"]""\n";
-
+
os << "\"" << &trie_node << "\"" << " -> " << "\"" << &(*subnode) << "\"" << "\n";
os << *subnode;
}
@@ -551,7 +588,7 @@
trie_iterator () : trie_ (0) {}
trie_iterator (typename Trie::iterator item) : trie_ (item) {}
trie_iterator (Trie &item) : trie_ (&item) {}
-
+
Trie & operator* () { return *trie_; }
const Trie & operator* () const { return *trie_; }
Trie * operator-> () { return trie_; }
@@ -560,7 +597,7 @@
bool operator== (trie_iterator<Trie, NonConstTrie> &other) { return (trie_ == other.trie_); }
bool operator!= (trie_iterator<const Trie, NonConstTrie> &other) const { return !(*this == other); }
bool operator!= (trie_iterator<Trie, NonConstTrie> &other) { return !(*this == other); }
-
+
trie_iterator<Trie,NonConstTrie> &
operator++ (int)
{
@@ -576,13 +613,13 @@
{
(*this)++;
return *this;
- }
+ }
private:
typedef typename boost::mpl::if_< boost::is_same<Trie, NonConstTrie>,
typename Trie::unordered_set::iterator,
typename Trie::unordered_set::const_iterator>::type set_iterator;
-
+
Trie* goUp ()
{
if (trie_->parent_ != 0)
@@ -611,7 +648,7 @@
template<class Trie>
class trie_point_iterator
{
-private:
+private:
typedef typename boost::mpl::if_< boost::is_same<Trie, const Trie>,
typename Trie::unordered_set::const_iterator,
typename Trie::unordered_set::iterator>::type set_iterator;
@@ -626,7 +663,7 @@
else
trie_ = 0;
}
-
+
Trie & operator* () { return *trie_; }
const Trie & operator* () const { return *trie_; }
Trie * operator-> () { return trie_; }
@@ -635,7 +672,7 @@
bool operator== (trie_point_iterator<Trie> &other) { return (trie_ == other.trie_); }
bool operator!= (trie_point_iterator<const Trie> &other) const { return !(*this == other); }
bool operator!= (trie_point_iterator<Trie> &other) { return !(*this == other); }
-
+
trie_point_iterator<Trie> &
operator++ (int)
{
@@ -660,7 +697,7 @@
{
(*this)++;
return *this;
- }
+ }
private:
Trie *trie_;