Stats tree seems to work properly, including pruning of "empty" leaves
diff --git a/model/ccnx-name-components.cc b/model/ccnx-name-components.cc
index a79b6bb..a0a12da 100644
--- a/model/ccnx-name-components.cc
+++ b/model/ccnx-name-components.cc
@@ -50,6 +50,13 @@
is >> *this;
}
+CcnxNameComponents::CcnxNameComponents (const char *prefix)
+{
+ NS_ASSERT (prefix != 0);
+
+ istringstream is (prefix);
+ is >> *this;
+}
const std::list<std::string> &
CcnxNameComponents::GetComponents () const
diff --git a/model/ccnx-name-components.h b/model/ccnx-name-components.h
index eb4f8c1..622f51f 100644
--- a/model/ccnx-name-components.h
+++ b/model/ccnx-name-components.h
@@ -68,6 +68,13 @@
* @param[in] prefix A string representation of a prefix
*/
CcnxNameComponents (const std::string &prefix);
+
+ /**
+ * @brief Constructor
+ * Creates a prefix from the string (string is parsed using operator>>)
+ * @param[in] prefix A string representation of a prefix
+ */
+ CcnxNameComponents (const char *prefix);
/**
* \brief Generic Add method
diff --git a/model/ccnx-pit-entry.cc b/model/ccnx-pit-entry.cc
index 4b075ab..73f966c 100644
--- a/model/ccnx-pit-entry.cc
+++ b/model/ccnx-pit-entry.cc
@@ -41,10 +41,10 @@
Ptr<CcnxFibEntry> fibEntry)
: m_container (container)
, m_prefix (header->GetNamePtr ())
+ , m_fibEntry (fibEntry)
, m_expireTime (Simulator::Now () + (!header->GetInterestLifetime ().IsZero ()?
header->GetInterestLifetime ():
Seconds (1.0)))
- , m_fibEntry (fibEntry)
, m_maxRetxCount (0)
{
// note that if interest lifetime is not set, the behavior is undefined
diff --git a/model/ccnx-pit-entry.h b/model/ccnx-pit-entry.h
index beda5bb..1ccb6b4 100644
--- a/model/ccnx-pit-entry.h
+++ b/model/ccnx-pit-entry.h
@@ -84,7 +84,7 @@
*
* All set-methods are virtual, in case index rearrangement is necessary in the derived classes
*/
-struct CcnxPitEntry : SimpleRefCount<CcnxPitEntry>
+class CcnxPitEntry : public SimpleRefCount<CcnxPitEntry>
{
public:
typedef std::set< CcnxPitEntryIncomingFace > in_container; ///< @brief incoming faces container type
diff --git a/test/ndnSIM-stats-tree.cc b/test/ndnSIM-stats-tree.cc
index 8e522c5..15a2030 100644
--- a/test/ndnSIM-stats-tree.cc
+++ b/test/ndnSIM-stats-tree.cc
@@ -51,7 +51,7 @@
node1->GetObject<Ccnx> ()->AddFace (face2);
node1->GetObject<Ccnx> ()->AddFace (face3);
- NS_LOG_DEBUG (*face1 << ", " << *face2 << ", " << *face3);
+ // NS_LOG_DEBUG (*face1 << ", " << *face2 << ", " << *face3);
NS_TEST_ASSERT_MSG_NE (*face1, *face2, "Face1 should not be equal to Face2");
NS_TEST_ASSERT_MSG_NE (face1, face2, "&Face1 should not be equal to &Face2");
@@ -90,25 +90,25 @@
NS_TEST_ASSERT_MSG_EQ (node.incoming ().size (), 2, "Incoming should have two entries again");
NS_TEST_ASSERT_MSG_EQ (node.outgoing ().size (), 0, "Outgoing should have 0 entries");
- NS_LOG_DEBUG ("count: " << node.incoming ().find (face1)->second.count ());
- NS_LOG_DEBUG ("satisfied: " << node.incoming ().find (face1)->second.satisfied ());
- NS_LOG_DEBUG ("unsatisfied:" << node.incoming ().find (face1)->second.unsatisfied ());
+ // NS_LOG_DEBUG ("count: " << node.incoming ().find (face1)->second.count ());
+ // NS_LOG_DEBUG ("satisfied: " << node.incoming ().find (face1)->second.satisfied ());
+ // NS_LOG_DEBUG ("unsatisfied:" << node.incoming ().find (face1)->second.unsatisfied ());
node.Step ();
- NS_LOG_DEBUG ("count: " << node.incoming ().find (face1)->second.count ());
- NS_LOG_DEBUG ("satisfied: " << node.incoming ().find (face1)->second.satisfied ());
- NS_LOG_DEBUG ("unsatisfied:" << node.incoming ().find (face1)->second.unsatisfied ());
+ // NS_LOG_DEBUG ("count: " << node.incoming ().find (face1)->second.count ());
+ // NS_LOG_DEBUG ("satisfied: " << node.incoming ().find (face1)->second.satisfied ());
+ // NS_LOG_DEBUG ("unsatisfied:" << node.incoming ().find (face1)->second.unsatisfied ());
LoadStats::stats_tuple tuple = node.incoming ().find (face1)->second.GetSatisfiedRatio ();
- NS_LOG_DEBUG ("In, face1, satisfied ratio: " << tuple.get<0> () << ", " << tuple.get<1> () << ", " << tuple.get<2> ());
+ // NS_LOG_DEBUG ("In, face1, satisfied ratio: " << tuple.get<0> () << ", " << tuple.get<1> () << ", " << tuple.get<2> ());
NS_TEST_ASSERT_MSG_EQ_TOL (tuple.get<0> (), 0.667, 0.01, "Satisfied ratio should be ~ 2/3");
NS_TEST_ASSERT_MSG_EQ_TOL (tuple.get<1> (), 0.667, 0.01, "Satisfied ratio should be ~ 2/3");
NS_TEST_ASSERT_MSG_EQ_TOL (tuple.get<2> (), 0.667, 0.01, "Satisfied ratio should be ~ 2/3");
tuple = node.incoming ().find (face1)->second.GetUnsatisfiedRatio ();
- NS_LOG_DEBUG ("In, face1, unsatisfied ratio: " << tuple.get<0> () << ", " << tuple.get<1> () << ", " << tuple.get<2> ());
+ // NS_LOG_DEBUG ("In, face1, unsatisfied ratio: " << tuple.get<0> () << ", " << tuple.get<1> () << ", " << tuple.get<2> ());
NS_TEST_ASSERT_MSG_EQ_TOL (tuple.get<0> (), 0.333, 0.01, "Satisfied ratio should be ~ 1/3");
NS_TEST_ASSERT_MSG_EQ_TOL (tuple.get<1> (), 0.333, 0.01, "Satisfied ratio should be ~ 1/3");
@@ -118,17 +118,17 @@
node.Timeout ();
node.Step ();
- NS_LOG_DEBUG ("After decaying");
+ // NS_LOG_DEBUG ("After decaying");
tuple = node.incoming ().find (face1)->second.GetSatisfiedRatio ();
- NS_LOG_DEBUG ("In, face1, satisfied ratio: " << tuple.get<0> () << ", " << tuple.get<1> () << ", " << tuple.get<2> ());
+ // NS_LOG_DEBUG ("In, face1, satisfied ratio: " << tuple.get<0> () << ", " << tuple.get<1> () << ", " << tuple.get<2> ());
NS_TEST_ASSERT_MSG_EQ_TOL (tuple.get<0> (), 0.489, 0.01, "");
NS_TEST_ASSERT_MSG_EQ_TOL (tuple.get<1> (), 0.489, 0.01, "");
NS_TEST_ASSERT_MSG_EQ_TOL (tuple.get<2> (), 0.489, 0.01, "");
tuple = node.incoming ().find (face1)->second.GetUnsatisfiedRatio ();
- NS_LOG_DEBUG ("In, face1, unsatisfied ratio: " << tuple.get<0> () << ", " << tuple.get<1> () << ", " << tuple.get<2> ());
+ // NS_LOG_DEBUG ("In, face1, unsatisfied ratio: " << tuple.get<0> () << ", " << tuple.get<1> () << ", " << tuple.get<2> ());
NS_TEST_ASSERT_MSG_EQ_TOL (tuple.get<0> (), 0.51, 0.01, "");
NS_TEST_ASSERT_MSG_EQ_TOL (tuple.get<1> (), 0.51, 0.01, "");
@@ -137,17 +137,17 @@
for (uint32_t i = 0; i < 50; i++ )
node.Step ();
- NS_LOG_DEBUG ("After more decaying");
+ // NS_LOG_DEBUG ("After more decaying");
tuple = node.incoming ().find (face1)->second.GetSatisfiedRatio ();
- NS_LOG_DEBUG ("In, face1, satisfied ratio: " << tuple.get<0> () << ", " << tuple.get<1> () << ", " << tuple.get<2> ());
+ // NS_LOG_DEBUG ("In, face1, satisfied ratio: " << tuple.get<0> () << ", " << tuple.get<1> () << ", " << tuple.get<2> ());
NS_TEST_ASSERT_MSG_EQ_TOL (tuple.get<0> (), 0.228, 0.01, "");
NS_TEST_ASSERT_MSG_EQ_TOL (tuple.get<1> (), 0.047, 0.01, "");
NS_TEST_ASSERT_MSG_EQ_TOL (tuple.get<2> (), 0.015, 0.01, "");
tuple = node.incoming ().find (face1)->second.GetUnsatisfiedRatio ();
- NS_LOG_DEBUG ("In, face1, unsatisfied ratio: " << tuple.get<0> () << ", " << tuple.get<1> () << ", " << tuple.get<2> ());
+ // NS_LOG_DEBUG ("In, face1, unsatisfied ratio: " << tuple.get<0> () << ", " << tuple.get<1> () << ", " << tuple.get<2> ());
NS_TEST_ASSERT_MSG_EQ_TOL (tuple.get<0> (), 0.238, 0.01, "");
NS_TEST_ASSERT_MSG_EQ_TOL (tuple.get<1> (), 0.049, 0.01, "");
@@ -158,19 +158,35 @@
/////////////////////////////////////////////////////
StatsTree tree;
- tree.NewPitEntry (CcnxNameComponents ("/bla/bla/bla"));
- tree.NewPitEntry (CcnxNameComponents ("/foo/bar"));
- tree.NewPitEntry (CcnxNameComponents ("/bar/foo"));
- tree.NewPitEntry (CcnxNameComponents ("/tra/la/la"));
+ tree.NewPitEntry ("/bla/bla/bla");
+ tree.NewPitEntry ("/bla/bla/bla");
+ tree.NewPitEntry ("/bla/bla/bla");
+ tree.NewPitEntry ("/foo/bar");
+ tree.NewPitEntry ("/bar/foo");
+ tree.NewPitEntry ("/tra/la/la");
- tree.Incoming (CcnxNameComponents ("/bla/bla/bla"), face1);
- tree.Outgoing (CcnxNameComponents ("/foo/bar"), face2);
- tree.Satisfy (CcnxNameComponents ("/bar/foo"));
- tree.Satisfy (CcnxNameComponents ("/tra/la/la"));
+ tree.Incoming ("/bla/bla/bla", face1);
+ tree.Outgoing ("/foo/bar", face2);
+ tree.Satisfy ("/bar/foo");
+ tree.Satisfy ("/tra/la/la");
+ tree.Timeout ("/tra/la/la");
tree.Step ();
-
- NS_LOG_DEBUG (tree);
+
+ NS_TEST_ASSERT_MSG_EQ (boost::lexical_cast<std::string> (tree ["/"]),
+ "PIT: 0.479734, 0.0991713, 0.0332409/0.159911, 0.0330571, 0.0110803/0.0799556, 0.0165285, 0.00554015",
+ "Something wrong with stats tree");
+
+ NS_TEST_ASSERT_MSG_NE (&tree ["/bla/bla/bla"],
+ &tree ["/"],
+ "The stats tree should not be empty");
+ for (uint32_t i = 0; i < 150; i++)
+ {
+ tree.Step ();
+ }
+ NS_TEST_ASSERT_MSG_EQ (&tree ["/bla/bla/bla"],
+ &tree ["/"],
+ "The stats tree should be empty (only root node)");
}
}
diff --git a/utils/load-stats-face.cc b/utils/load-stats-face.cc
index 834004a..2e66197 100644
--- a/utils/load-stats-face.cc
+++ b/utils/load-stats-face.cc
@@ -58,6 +58,12 @@
return *this;
}
+bool
+LoadStatsFace::IsZero () const
+{
+ return m_count.IsZero () && m_satisfied.IsZero () && m_unsatisfied.IsZero ();
+}
+
std::ostream &
operator << (std::ostream &os, const LoadStatsFace &stats)
{
diff --git a/utils/load-stats-face.h b/utils/load-stats-face.h
index ad033b4..6c85a68 100644
--- a/utils/load-stats-face.h
+++ b/utils/load-stats-face.h
@@ -59,6 +59,9 @@
LoadStatsFace &
operator += (const LoadStatsFace &load);
+
+ bool
+ IsZero () const;
private:
LoadStats m_count;
diff --git a/utils/load-stats-node.cc b/utils/load-stats-node.cc
index 34875c5..59184c8 100644
--- a/utils/load-stats-node.cc
+++ b/utils/load-stats-node.cc
@@ -20,15 +20,24 @@
#include "load-stats-node.h"
#include "ns3/ccnx-face.h"
+#include "ns3/log.h"
+#include <boost/lambda/lambda.hpp>
+#include <boost/lambda/bind.hpp>
+
+namespace ll = boost::lambda;
using namespace ns3;
+NS_LOG_COMPONENT_DEFINE ("LoadStatsNode");
+
namespace ndnSIM
{
void
LoadStatsNode::Step ()
{
+ NS_LOG_FUNCTION (this);
+
m_pit.Step ();
for (stats_container::iterator item = m_incoming.begin ();
@@ -107,6 +116,8 @@
LoadStatsNode &
LoadStatsNode::operator += (const LoadStatsNode &stats)
{
+ NS_LOG_FUNCTION (this << &stats);
+
m_pit += stats.m_pit;
// aggregate incoming
@@ -128,10 +139,37 @@
return *this;
}
+bool
+LoadStatsNode::IsZero () const
+{
+ bool zero = true;
+ std::for_each (m_incoming.begin (), m_incoming.end (),
+ zero &= ll::bind (&LoadStatsFace::IsZero,
+ ll::bind (&stats_container::value_type::second, ll::_1)));
+
+ std::for_each (m_outgoing.begin (), m_outgoing.end (),
+ zero &= ll::bind (&LoadStatsFace::IsZero,
+ ll::bind (&stats_container::value_type::second, ll::_1)));
+ zero &= m_pit.IsZero ();
+
+ return zero;
+}
+
+bool
+LoadStatsNode::operator == (const LoadStatsNode &other) const
+{
+ if (other.m_incoming.size () > 0 ||
+ other.m_outgoing.size () > 0 ||
+ !other.m_pit.IsZero ())
+ return false;
+
+ return IsZero ();
+}
+
std::ostream&
operator << (std::ostream &os, const LoadStatsNode &node)
{
- os << "PIT: " << node.m_pit << std::endl;
+ os << "PIT: " << node.m_pit;// << std::endl;
return os;
}
diff --git a/utils/load-stats-node.h b/utils/load-stats-node.h
index 5376144..e91b094 100644
--- a/utils/load-stats-node.h
+++ b/utils/load-stats-node.h
@@ -89,15 +89,15 @@
pit () const;
bool
- operator == (const LoadStatsNode &other) const
- {
- return false;
- }
-
+ IsZero () const;
+
+ bool
+ operator == (const LoadStatsNode &other) const;
+
bool
operator != (const LoadStatsNode &other) const
{
- return true;
+ return !(*this == other);
}
LoadStatsNode &
diff --git a/utils/load-stats.cc b/utils/load-stats.cc
index ee61df4..8a663e3 100644
--- a/utils/load-stats.cc
+++ b/utils/load-stats.cc
@@ -19,6 +19,7 @@
*/
#include "load-stats.h"
+#include "ns3/log.h"
using namespace ns3;
@@ -28,6 +29,8 @@
const double EPSILON = 0.000001;
+NS_LOG_COMPONENT_DEFINE ("LoadStats");
+
namespace ndnSIM
{
@@ -42,6 +45,8 @@
void
LoadStats::Step ()
{
+ // NS_LOG_FUNCTION (this);
+
// do magic
avg1_ = EXP_1 * avg1_ + (1 - EXP_1) * counter_;
avg5_ = EXP_1 * avg5_ + (1 - EXP_5) * counter_;
@@ -53,25 +58,17 @@
LoadStats &
LoadStats::operator ++ (int)
{
+ // NS_LOG_FUNCTION (this);
+
counter_ ++;
return *this;
}
-// void
-// LoadStats::Increment (uint32_t amount)
-// {
-// counter_ += amount;
-// }
-
-// uint32_t
-// LoadStats::GetCounter () const
-// {
-// return counter_;
-// }
-
LoadStats &
LoadStats::operator += (const LoadStats &stats)
{
+ // NS_LOG_FUNCTION (this << &stats << stats.counter_);
+
counter_ += stats.counter_;
return *this;
}
@@ -83,9 +80,10 @@
}
bool
-LoadStats::IsEmpty () const
+LoadStats::IsZero () const
{
- return (avg1_ < EPSILON &&
+ return (counter_ == 0 &&
+ avg1_ < EPSILON &&
avg5_ < EPSILON &&
avg15_ < EPSILON);
}
@@ -93,8 +91,7 @@
std::ostream &
operator << (std::ostream &os, const LoadStats &stats)
{
- LoadStats::stats_tuple data = stats.GetStats ();
- os << data.get<0> () << ", " << data.get<1> () << ", " << data.get<2> ();// << std::endl;
+ os << stats.avg1_ << ", " << stats.avg5_ << ", " << stats.avg15_;
return os;
}
diff --git a/utils/load-stats.h b/utils/load-stats.h
index 8b2433e..a9f2e5f 100644
--- a/utils/load-stats.h
+++ b/utils/load-stats.h
@@ -53,7 +53,7 @@
GetStats () const;
bool
- IsEmpty () const;
+ IsZero () const;
private:
uint32_t counter_;
@@ -61,6 +61,9 @@
double avg1_;
double avg5_;
double avg15_;
+
+ friend std::ostream &
+ operator << (std::ostream &os, const LoadStats &stats);
};
std::ostream &
diff --git a/utils/stats-tree.cc b/utils/stats-tree.cc
index eb37c02..6d2ff28 100644
--- a/utils/stats-tree.cc
+++ b/utils/stats-tree.cc
@@ -37,27 +37,28 @@
void
StatsTree::Step ()
{
+ NS_LOG_FUNCTION (this);
+
// walking the tree, aggregating and stepping on every node, starting the leaves
// for (trie_type::
WalkLeftRightRoot (&m_tree);
+ m_tree.payload ().Step ();
+ NS_LOG_DEBUG ("[" << m_tree.key () << "] " << m_tree.payload ());
}
void
StatsTree::NewPitEntry (const ns3::CcnxNameComponents &key)
{
std::pair<tree_type::iterator, bool> item = m_tree.insert (key, LoadStatsNode ());
- NS_ASSERT (item.second == false); // should always return false
item.first->payload ().NewPitEntry ();
- NS_LOG_DEBUG ("NewPitEntry: " << item.first->payload ());
}
void
StatsTree::Incoming (const CcnxNameComponents &key, Ptr<CcnxFace> face)
{
std::pair<tree_type::iterator, bool> item = m_tree.insert (key, LoadStatsNode ());
- NS_ASSERT (item.second == false); // should always return false
item.first->payload ().AddIncoming (face);
}
@@ -66,7 +67,6 @@
StatsTree::Outgoing (const CcnxNameComponents &key, Ptr<CcnxFace> face)
{
std::pair<tree_type::iterator, bool> item = m_tree.insert (key, LoadStatsNode ());
- NS_ASSERT (item.second == false); // should always return false
item.first->payload ().AddOutgoing (face);
}
@@ -75,7 +75,6 @@
StatsTree::Satisfy (const CcnxNameComponents &key)
{
std::pair<tree_type::iterator, bool> item = m_tree.insert (key, LoadStatsNode ());
- NS_ASSERT (item.second == false); // should always return false
item.first->payload ().Satisfy ();
}
@@ -84,42 +83,49 @@
StatsTree::Timeout (const CcnxNameComponents &key)
{
std::pair<tree_type::iterator, bool> item = m_tree.insert (key, LoadStatsNode ());
- NS_ASSERT (item.second == false); // should always return false
item.first->payload ().Timeout ();
}
+// const LoadStatsNode &
+// StatsTree::Get (const ns3::CcnxNameComponents &key) const
const LoadStatsNode &
-StatsTree::Get (const ns3::CcnxNameComponents &key) const
+StatsTree::operator [] (const ns3::CcnxNameComponents &key) const
{
tree_type::iterator foundItem, lastItem;
bool reachLast;
boost::tie (foundItem, reachLast, lastItem) = const_cast<tree_type&> (m_tree).find (key);
- NS_ASSERT_MSG (foundItem == lastItem, "Found item should always be the same as last item (same address)");
-
- return foundItem->payload ();
+ return lastItem->payload ();
}
const LoadStatsNode&
StatsTree::WalkLeftRightRoot (tree_type *node)
{
tree_type::point_iterator item (*node), end;
-
- for (; item != end; item++)
+
+ while (item != end)
{
node->payload () += WalkLeftRightRoot (&*item);
- NS_LOG_DEBUG (node << ", " << node->payload ());
- }
+ item->payload ().Step ();
- node->payload ().Step ();
+ NS_LOG_DEBUG ("[" << item->key () << "] " << item->payload ());
+ // item->prune (); // will do only if necessary
+
+ tree_type::point_iterator prune_iterator = item;
+ item++;
+
+ prune_iterator->prune ();
+ }
+
return node->payload ();
}
std::ostream &
operator << (std::ostream &os, const StatsTree &tree)
{
- os << tree.m_tree.payload ();
+ // os << "[" << tree.m_tree.key () << "]: " << tree.m_tree.payload ();
+ os << tree.m_tree;
return os;
}
diff --git a/utils/stats-tree.h b/utils/stats-tree.h
index e731d32..1f9d146 100644
--- a/utils/stats-tree.h
+++ b/utils/stats-tree.h
@@ -55,8 +55,10 @@
void
Timeout (const ns3::CcnxNameComponents &key);
+ // const LoadStatsNode &
+ // Get (const ns3::CcnxNameComponents &key) const;
const LoadStatsNode &
- Get (const ns3::CcnxNameComponents &key) const;
+ operator [] (const ns3::CcnxNameComponents &key) const;
private:
const LoadStatsNode &
diff --git a/utils/trie.h b/utils/trie.h
index 51a7678..dbd3e1d 100644
--- a/utils/trie.h
+++ b/utils/trie.h
@@ -377,6 +377,11 @@
{
payload_ = payload;
}
+
+ Key key () const
+ {
+ return key_;
+ }
inline void
PrintStat (std::ostream &os) const;