Implementing base support for TCP-style window-based limiting on per-FIB-prefix and per-face granularity
Currently, limits are supported only by ndn::fw::Limits forwarding
strategy and only at the very basic (not fully tested) level.
diff --git a/helper/ndn-stack-helper.cc b/helper/ndn-stack-helper.cc
index 9fcc8f2..d84b86b 100644
--- a/helper/ndn-stack-helper.cc
+++ b/helper/ndn-stack-helper.cc
@@ -270,6 +270,8 @@
NS_LOG_INFO ("Max packets per second: " << maxInterestPackets);
NS_LOG_INFO ("Max burst: " << m_avgRtt.ToDouble (Time::S) * maxInterestPackets);
+ // Set max to BDP
+ face->GetLimits ()->SetMaxLimit (m_avgRtt.ToDouble (Time::S) * maxInterestPackets);
}
}
diff --git a/model/fib/ndn-fib-entry.cc b/model/fib/ndn-fib-entry.cc
index 01e2970..750f9da 100644
--- a/model/fib/ndn-fib-entry.cc
+++ b/model/fib/ndn-fib-entry.cc
@@ -22,6 +22,7 @@
#include "ns3/ndn-name-components.h"
#include "ns3/log.h"
+#include "ns3/simulator.h"
#define NDN_RTO_ALPHA 0.125
#define NDN_RTO_BETA 0.25
diff --git a/model/fib/ndn-fib-entry.h b/model/fib/ndn-fib-entry.h
index 532120f..c8072f4 100644
--- a/model/fib/ndn-fib-entry.h
+++ b/model/fib/ndn-fib-entry.h
@@ -25,6 +25,7 @@
#include "ns3/nstime.h"
#include "ns3/ndn-face.h"
#include "ns3/ndn-name-components.h"
+#include "ns3/ndn-limits.h"
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/tag.hpp>
@@ -176,7 +177,9 @@
Entry (const Ptr<const NameComponents> &prefix)
: m_prefix (prefix)
, m_needsProbing (false)
- { }
+ {
+ m_limits = CreateObject<Limits> ();
+ }
/**
* \brief Update status of FIB next hop
@@ -227,7 +230,16 @@
{
m_faces.erase (face);
}
-
+
+ /**
+ * @brief Get reference to limits object
+ */
+ Limits &
+ GetLimits ()
+ {
+ return *m_limits;
+ }
+
private:
friend std::ostream& operator<< (std::ostream& os, const Entry &entry);
@@ -235,7 +247,9 @@
Ptr<const NameComponents> m_prefix; ///< \brief Prefix of the FIB entry
FaceMetricContainer::type m_faces; ///< \brief Indexed list of faces
- bool m_needsProbing; ///< \brief flag indicating that probing should be performed
+ bool m_needsProbing; ///< \brief flag indicating that probing should be performed
+
+ Ptr<Limits> m_limits;
};
std::ostream& operator<< (std::ostream& os, const Entry &entry);
diff --git a/model/fib/ndn-fib-impl.cc b/model/fib/ndn-fib-impl.cc
index b91e94c..fd12c68 100644
--- a/model/fib/ndn-fib-impl.cc
+++ b/model/fib/ndn-fib-impl.cc
@@ -208,7 +208,7 @@
}
Ptr<const Entry>
-FibImpl::Begin ()
+FibImpl::Begin () const
{
super::parent_trie::const_recursive_iterator item (super::getTrie ());
super::parent_trie::const_recursive_iterator end (0);
@@ -225,13 +225,13 @@
}
Ptr<const Entry>
-FibImpl::End ()
+FibImpl::End () const
{
return 0;
}
Ptr<const Entry>
-FibImpl::Next (Ptr<const Entry> from)
+FibImpl::Next (Ptr<const Entry> from) const
{
if (from == 0) return 0;
@@ -249,6 +249,49 @@
return item->payload ();
}
+Ptr<Entry>
+FibImpl::Begin ()
+{
+ super::parent_trie::recursive_iterator item (super::getTrie ());
+ super::parent_trie::recursive_iterator end (0);
+ for (; item != end; item++)
+ {
+ if (item->payload () == 0) continue;
+ break;
+ }
+
+ if (item == end)
+ return End ();
+ else
+ return item->payload ();
+}
+
+Ptr<Entry>
+FibImpl::End ()
+{
+ return 0;
+}
+
+Ptr<Entry>
+FibImpl::Next (Ptr<Entry> from)
+{
+ if (from == 0) return 0;
+
+ super::parent_trie::recursive_iterator item (*StaticCast<EntryImpl> (from)->to_iterator ());
+ super::parent_trie::recursive_iterator end (0);
+ for (item++; item != end; item++)
+ {
+ if (item->payload () == 0) continue;
+ break;
+ }
+
+ if (item == end)
+ return End ();
+ else
+ return item->payload ();
+}
+
+
} // namespace fib
} // namespace ndn
} // namespace ns3
diff --git a/model/fib/ndn-fib-impl.h b/model/fib/ndn-fib-impl.h
index 4c78997..1efead9 100644
--- a/model/fib/ndn-fib-impl.h
+++ b/model/fib/ndn-fib-impl.h
@@ -110,13 +110,22 @@
GetSize () const;
virtual Ptr<const Entry>
+ Begin () const;
+
+ virtual Ptr<Entry>
Begin ();
virtual Ptr<const Entry>
+ End () const;
+
+ virtual Ptr<Entry>
End ();
virtual Ptr<const Entry>
- Next (Ptr<const Entry> item);
+ Next (Ptr<const Entry> item) const;
+
+ virtual Ptr<Entry>
+ Next (Ptr<Entry> item);
protected:
// inherited from Object class
diff --git a/model/fib/ndn-fib.h b/model/fib/ndn-fib.h
index b1b4be7..951f2cb 100644
--- a/model/fib/ndn-fib.h
+++ b/model/fib/ndn-fib.h
@@ -142,19 +142,37 @@
* @brief Return first element of FIB (no order guaranteed)
*/
virtual Ptr<const fib::Entry>
- Begin () = 0;
+ Begin () const = 0;
+
+ /**
+ * @brief Return first element of FIB (no order guaranteed)
+ */
+ virtual Ptr<fib::Entry>
+ Begin () = 0;
/**
* @brief Return item next after last (no order guaranteed)
*/
virtual Ptr<const fib::Entry>
+ End () const = 0;
+
+ /**
+ * @brief Return item next after last (no order guaranteed)
+ */
+ virtual Ptr<fib::Entry>
End () = 0;
/**
* @brief Advance the iterator
*/
virtual Ptr<const fib::Entry>
- Next (Ptr<const fib::Entry>) = 0;
+ Next (Ptr<const fib::Entry>) const = 0;
+
+ /**
+ * @brief Advance the iterator
+ */
+ virtual Ptr<fib::Entry>
+ Next (Ptr<fib::Entry>) = 0;
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
diff --git a/model/fw/fw-stats.cc b/model/fw/fw-stats.cc
index de30473..959d25f 100644
--- a/model/fw/fw-stats.cc
+++ b/model/fw/fw-stats.cc
@@ -167,9 +167,9 @@
void
-FwStats::WillErasePendingInterest (Ptr<pit::Entry> pitEntry)
+FwStats::WillEraseTimedOutPendingInterest (Ptr<pit::Entry> pitEntry)
{
- super::WillErasePendingInterest (pitEntry);
+ super::WillEraseTimedOutPendingInterest (pitEntry);
m_stats.Timeout (pitEntry->GetPrefix ().cut (1));
diff --git a/model/fw/fw-stats.h b/model/fw/fw-stats.h
index 2b8cae9..1a516d8 100644
--- a/model/fw/fw-stats.h
+++ b/model/fw/fw-stats.h
@@ -94,7 +94,7 @@
const Ptr<const Packet> &packet);
virtual void
- WillErasePendingInterest (Ptr<pit::Entry> pitEntry);
+ WillEraseTimedOutPendingInterest (Ptr<pit::Entry> pitEntry);
// from Object
void
diff --git a/model/fw/nacks.h b/model/fw/nacks.h
index e9226ad..4e7da4e 100644
--- a/model/fw/nacks.h
+++ b/model/fw/nacks.h
@@ -51,8 +51,6 @@
const Ptr<const Packet> &p);
protected:
- // using NdnForwardingStrategy::PropagateInterest; // some strange c++ cheating
-
virtual void
DidReceiveDuplicateInterest (const Ptr<Face> &face,
Ptr<InterestHeader> &header,
diff --git a/model/fw/ndn-forwarding-strategy.cc b/model/fw/ndn-forwarding-strategy.cc
index 1cbcd09..cf09878 100644
--- a/model/fw/ndn-forwarding-strategy.cc
+++ b/model/fw/ndn-forwarding-strategy.cc
@@ -427,8 +427,8 @@
bool
ForwardingStrategy::WillSendOutInterest (const Ptr<Face> &outgoingFace,
- Ptr<InterestHeader> header,
- Ptr<pit::Entry> pitEntry)
+ Ptr<InterestHeader> header,
+ Ptr<pit::Entry> pitEntry)
{
pit::Entry::out_iterator outgoing =
pitEntry->GetOutgoing ().find (outgoingFace);
@@ -462,7 +462,7 @@
}
void
-ForwardingStrategy::WillErasePendingInterest (Ptr<pit::Entry> pitEntry)
+ForwardingStrategy::WillEraseTimedOutPendingInterest (Ptr<pit::Entry> pitEntry)
{
// do nothing for now. may be need to do some logging
}
diff --git a/model/fw/ndn-forwarding-strategy.h b/model/fw/ndn-forwarding-strategy.h
index 1d4111e..75f6647 100644
--- a/model/fw/ndn-forwarding-strategy.h
+++ b/model/fw/ndn-forwarding-strategy.h
@@ -82,9 +82,19 @@
Ptr<Packet> &payload,
const Ptr<const Packet> &packet);
+ /**
+ * @brief Event fired just before PIT entry is removed by timeout
+ * @param pitEntry PIT entry to be removed
+ */
virtual void
- WillErasePendingInterest (Ptr<pit::Entry> pitEntry);
+ WillEraseTimedOutPendingInterest (Ptr<pit::Entry> pitEntry);
+ /**
+ * @brief Event fired every time face is removed from NDN stack
+ * @param face face to be removed
+ *
+ * For example, when an application terminates, AppFace is removed and this method called by NDN stack.
+ */
virtual void
RemoveFace (Ptr<Face> face);
diff --git a/model/fw/per-fib-limits.cc b/model/fw/per-fib-limits.cc
new file mode 100644
index 0000000..77851bc
--- /dev/null
+++ b/model/fw/per-fib-limits.cc
@@ -0,0 +1,168 @@
+/* -*- 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>
+ * Ilya Moiseenko <iliamo@cs.ucla.edu>
+ */
+
+#include "per-fib-limits.h"
+
+#include "ns3/ndn-interest-header.h"
+#include "ns3/ndn-content-object-header.h"
+#include "ns3/ndn-pit.h"
+#include "ns3/ndn-pit-entry.h"
+
+#include "ns3/assert.h"
+#include "ns3/log.h"
+#include "ns3/simulator.h"
+
+#include <boost/foreach.hpp>
+#include <boost/lambda/lambda.hpp>
+#include <boost/lambda/bind.hpp>
+namespace ll = boost::lambda;
+
+NS_LOG_COMPONENT_DEFINE ("ndn.fw.PerFibLimits");
+
+namespace ns3 {
+namespace ndn {
+namespace fw {
+
+NS_OBJECT_ENSURE_REGISTERED (PerFibLimits);
+
+TypeId
+PerFibLimits::GetTypeId (void)
+{
+ static TypeId tid = TypeId ("ns3::ndn::fw::PerFibLimits")
+ .SetGroupName ("Ndn")
+ .SetParent <FwStats> ()
+ .AddConstructor <PerFibLimits> ()
+ ;
+ return tid;
+}
+
+PerFibLimits::PerFibLimits ()
+{
+}
+
+void
+PerFibLimits::DoDispose ()
+{
+ BestRoute::DoDispose ();
+ m_decayLimitsEvent.Cancel ();
+}
+
+bool
+PerFibLimits::WillSendOutInterest (const Ptr<Face> &outgoingFace,
+ Ptr<InterestHeader> header,
+ Ptr<pit::Entry> pitEntry)
+{
+ NS_LOG_FUNCTION (this << pitEntry->GetPrefix ());
+ // override all (if any) parent processing
+
+ pit::Entry::out_iterator outgoing =
+ pitEntry->GetOutgoing ().find (outgoingFace);
+
+ if (outgoing != pitEntry->GetOutgoing ().end ())
+ {
+ return false;
+ }
+
+ if (pitEntry->GetFibEntry ()->GetLimits ().IsBelowLimit ())
+ {
+ if (outgoingFace->GetLimits ()->IsBelowLimit ())
+ {
+ pitEntry->AddOutgoing (outgoingFace);
+ return true;
+ }
+ else
+ {
+ pitEntry->GetFibEntry ()->GetLimits ().RemoveOutstanding ();
+ }
+ }
+
+ return false;
+}
+
+void
+PerFibLimits::WillEraseTimedOutPendingInterest (Ptr<pit::Entry> pitEntry)
+{
+ NS_LOG_FUNCTION (this << pitEntry->GetPrefix ());
+
+ for (pit::Entry::out_container::iterator face = pitEntry->GetOutgoing ().begin ();
+ face != pitEntry->GetOutgoing ().end ();
+ face ++)
+ {
+ face->m_face->GetLimits ()->RemoveOutstanding ();
+ // face->m_face->GetLimits ()->DecreaseLimit (); !!! do not decrease per-face limit. it doesn't make sense !!!
+ }
+
+ pitEntry->GetFibEntry ()->GetLimits ().RemoveOutstanding ();
+ pitEntry->GetFibEntry ()->GetLimits ().DecreaseLimit (); // multiplicative decrease
+
+ if (!m_decayLimitsEvent.IsRunning ())
+ m_decayLimitsEvent = Simulator::Schedule (Seconds (1.0), &PerFibLimits::DecayLimits, this);
+}
+
+
+void
+PerFibLimits::WillSatisfyPendingInterest (const Ptr<Face> &incomingFace,
+ Ptr<pit::Entry> pitEntry)
+{
+ NS_LOG_FUNCTION (this << pitEntry->GetPrefix ());
+
+ super::WillSatisfyPendingInterest (incomingFace, pitEntry);
+
+ for (pit::Entry::out_container::iterator face = pitEntry->GetOutgoing ().begin ();
+ face != pitEntry->GetOutgoing ().end ();
+ face ++)
+ {
+ face->m_face->GetLimits ()->RemoveOutstanding ();
+ // face->m_face->GetLimits ()->IncreaseLimit (); !!! do not increase (as do not decrease) per-face limit. again, it doesn't make sense
+ }
+
+ pitEntry->GetFibEntry ()->GetLimits ().RemoveOutstanding ();
+ pitEntry->GetFibEntry ()->GetLimits ().IncreaseLimit (); // additive increase
+}
+
+
+// void
+// PerFibLimits::DidReceiveValidNack (const Ptr<Face> &incomingFace,
+// uint32_t nackCode,
+// Ptr<pit::Entry> pitEntry)
+// {
+// // super::DidReceiveValidNack (incomingFace, nackCode, pitEntry);
+
+// // ??
+// }
+
+void
+PerFibLimits::DecayLimits ()
+{
+ for (Ptr<fib::Entry> entry = m_fib->Begin ();
+ entry != m_fib->End ();
+ entry = m_fib->Next (entry))
+ {
+ entry->GetLimits ().DecayCurrentLimit ();
+ }
+
+ m_decayLimitsEvent = Simulator::Schedule (Seconds (1.0), &PerFibLimits::DecayLimits, this);
+}
+
+
+} // namespace fw
+} // namespace ndn
+} // namespace ns3
diff --git a/model/fw/per-fib-limits.h b/model/fw/per-fib-limits.h
new file mode 100644
index 0000000..2ee5141
--- /dev/null
+++ b/model/fw/per-fib-limits.h
@@ -0,0 +1,81 @@
+/* -*- 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 NDNSIM_PER_FIB_LIMITS_H
+#define NDNSIM_PER_FIB_LIMITS_H
+
+#include "ns3/event-id.h"
+
+#include "fw-stats.h"
+
+namespace ns3 {
+namespace ndn {
+namespace fw {
+
+/**
+ * \ingroup ndn
+ * \brief Strategy implementing per-FIB entry limits
+ */
+class PerFibLimits :
+ public FwStats
+{
+public:
+ static TypeId
+ GetTypeId ();
+
+ /**
+ * @brief Default constructor
+ */
+ PerFibLimits ();
+
+ virtual void
+ WillEraseTimedOutPendingInterest (Ptr<pit::Entry> pitEntry);
+
+protected:
+ virtual bool
+ WillSendOutInterest (const Ptr<Face> &outgoingFace,
+ Ptr<InterestHeader> header,
+ Ptr<pit::Entry> pitEntry);
+
+ virtual void
+ WillSatisfyPendingInterest (const Ptr<Face> &incomingFace,
+ Ptr<pit::Entry> pitEntry);
+
+ // from Object
+ void
+ DoDispose ();
+
+private:
+ void
+ DecayLimits ();
+
+private:
+ EventId m_decayLimitsEvent;
+
+ typedef FwStats super;
+};
+
+
+} // namespace fw
+} // namespace ndn
+} // namespace ns3
+
+#endif // NDNSIM_PER_FIB_LIMITS_H
diff --git a/model/ndn-face.cc b/model/ndn-face.cc
index ece32f5..9b5bc89 100644
--- a/model/ndn-face.cc
+++ b/model/ndn-face.cc
@@ -30,6 +30,7 @@
#include "ns3/boolean.h"
#include "ns3/simulator.h"
#include "ns3/random-variable.h"
+#include "ns3/pointer.h"
// #include "ns3/weights-path-stretch-tag.h"
@@ -54,20 +55,11 @@
MakeUintegerAccessor (&Face::m_id),
MakeUintegerChecker<uint32_t> ())
- .AddAttribute ("BucketMax", "Maximum size of leaky bucket",
- DoubleValue (-1.0),
- MakeDoubleAccessor (&Face::m_bucketMax),
- MakeDoubleChecker<double> ())
- .AddAttribute ("BucketLeak", "Normalized bucket leak size",
- DoubleValue (0.0),
- MakeDoubleAccessor (&Face::m_bucketLeak),
- MakeDoubleChecker<double> ())
+ .AddAttribute ("Limits", "Limits object",
+ PointerValue (CreateObject<Limits> ()),
+ MakePointerAccessor (&Face::m_limits),
+ MakePointerChecker<Limits> ())
- .AddAttribute ("RandomizeLimitChecking", "Whether or not to randomize the limit checking procedure. false (persistent) by default",
- BooleanValue (false),
- MakeBooleanAccessor (&Face::m_randomizeLimitChecking),
- MakeBooleanChecker ())
-
// .AddAttribute ("MetricTagging", "Enable metric tagging (path-stretch calculation)",
// BooleanValue (false),
// MakeBooleanAccessor (&Face::m_enableMetricTagging),
diff --git a/model/ndn-face.h b/model/ndn-face.h
index 6ed40bc..d22e073 100644
--- a/model/ndn-face.h
+++ b/model/ndn-face.h
@@ -29,6 +29,7 @@
#include "ns3/nstime.h"
#include "ns3/type-id.h"
#include "ns3/traced-callback.h"
+#include "ns3/ndn-limits.h"
namespace ns3 {
@@ -89,7 +90,10 @@
RegisterProtocolHandler (ProtocolHandler handler);
/**
+ * @brief Get reference to Limits object
*/
+ inline Ptr<Limits>
+ GetLimits ();
/**
* \brief Send packet on a face
@@ -217,6 +221,7 @@
uint32_t m_id; ///< \brief id of the interface in Ndn stack (per-node uniqueness)
uint32_t m_metric; ///< \brief metric of the face
+ Ptr<Limits> m_limits;
// bool m_enableMetricTagging;
TracedCallback<Ptr<const Packet> > m_txTrace;
@@ -250,6 +255,13 @@
return !(*this == face);
}
+inline Ptr<Limits>
+Face::GetLimits ()
+{
+ return m_limits;
+}
+
+
} // namespace ndn
} // namespace ns3
diff --git a/model/ndn-net-device-face.cc b/model/ndn-net-device-face.cc
index f5f38a0..7373ed8 100644
--- a/model/ndn-net-device-face.cc
+++ b/model/ndn-net-device-face.cc
@@ -38,6 +38,8 @@
namespace ns3 {
namespace ndn {
+NS_OBJECT_ENSURE_REGISTERED (NetDeviceFace);
+
TypeId
NetDeviceFace::GetTypeId ()
{
diff --git a/model/pit/ndn-pit-entry-incoming-face.cc b/model/pit/ndn-pit-entry-incoming-face.cc
index 5a7f518..5e3adce 100644
--- a/model/pit/ndn-pit-entry-incoming-face.cc
+++ b/model/pit/ndn-pit-entry-incoming-face.cc
@@ -43,7 +43,7 @@
* @brie Copy operator
*/
IncomingFace &
-IncomingFace::operator = (IncomingFace &other)
+IncomingFace::operator = (const IncomingFace &other)
{
m_face = other.m_face;
m_arrivalTime = other.m_arrivalTime;
diff --git a/model/pit/ndn-pit-entry-incoming-face.h b/model/pit/ndn-pit-entry-incoming-face.h
index 8ff7947..cd75643 100644
--- a/model/pit/ndn-pit-entry-incoming-face.h
+++ b/model/pit/ndn-pit-entry-incoming-face.h
@@ -55,7 +55,7 @@
* @brie Copy operator
*/
IncomingFace &
- operator = (IncomingFace &other);
+ operator = (const IncomingFace &other);
/**
* @brief Compare two PitEntryIncomingFace
diff --git a/model/pit/ndn-pit-impl.cc b/model/pit/ndn-pit-impl.cc
index da3f4f3..c1e5eb0 100644
--- a/model/pit/ndn-pit-impl.cc
+++ b/model/pit/ndn-pit-impl.cc
@@ -182,9 +182,9 @@
Time nextEvent = i_time.begin ()->GetExpireTime () - Simulator::Now ();
if (nextEvent <= 0) nextEvent = Seconds (0);
- // NS_LOG_DEBUG ("Schedule next cleaning in " <<
- // nextEvent.ToDouble (Time::S) << "s (at " <<
- // i_time.begin ()->GetExpireTime () << "s abs time");
+ NS_LOG_DEBUG ("Schedule next cleaning in " <<
+ nextEvent.ToDouble (Time::S) << "s (at " <<
+ i_time.begin ()->GetExpireTime () << "s abs time");
m_cleanEvent = Simulator::Schedule (nextEvent,
&PitImpl<Policy>::CleanExpired, this);
@@ -203,7 +203,7 @@
typename time_index::iterator entry = i_time.begin ();
if (entry->GetExpireTime () <= now) // is the record stale?
{
- m_forwardingStrategy->WillErasePendingInterest (entry->to_iterator ()->payload ());
+ m_forwardingStrategy->WillEraseTimedOutPendingInterest (entry->to_iterator ()->payload ());
super::erase (entry->to_iterator ());
// count ++;
}
diff --git a/test/fw-per-fib-limits.cc b/test/fw-per-fib-limits.cc
new file mode 100644
index 0000000..d66856e
--- /dev/null
+++ b/test/fw-per-fib-limits.cc
@@ -0,0 +1,156 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2011,2012 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 "fw-per-fib-limits.h"
+#include "ns3/core-module.h"
+#include "ns3/ndnSIM-module.h"
+#include "ns3/point-to-point-module.h"
+
+#include <boost/lexical_cast.hpp>
+
+NS_LOG_COMPONENT_DEFINE ("ndn.test.fw.PerFibLimits");
+
+namespace ns3 {
+namespace ndn {
+
+void Decay (Ptr<fib::Entry> entry)
+{
+ entry->GetLimits ().DecayCurrentLimit ();
+}
+
+
+template<class T>
+void
+PrintTracedValue (std::string context, T oldValue, T newValue)
+{
+ NS_LOG_DEBUG (context << ": " <<
+ oldValue << " => " << newValue);
+}
+
+void
+Test1 (Ptr<fib::Entry> entry)
+{
+ entry->GetLimits ().IsBelowLimit ();
+ entry->GetLimits ().DecreaseLimit ();
+}
+
+void
+Test2 (Ptr<fib::Entry> entry)
+{
+ entry->GetLimits ().RemoveOutstanding ();
+ for (uint32_t i = 0; i < 40; i++)
+ entry->GetLimits ().IncreaseLimit ();
+}
+
+void
+FwPerFibLimits::CheckCurMaxLimit (Ptr<fib::Entry> entry, double amount)
+{
+ NS_TEST_ASSERT_MSG_EQ_TOL ((double)entry->GetLimits ().m_curMaxLimit, amount, 0.1, "");
+}
+
+void
+FwPerFibLimits::CheckOutstanding (Ptr<fib::Entry> entry, uint32_t amount)
+{
+ NS_TEST_ASSERT_MSG_EQ ((double)entry->GetLimits ().m_outstanding, amount, "");
+}
+
+// void
+// FwPerFibLimits::Check2 (Ptr<fib::Entry> entry)
+// {
+// NS_TEST_ASSERT_MSG_EQ ((double)entry->GetLimits ().m_outstanding, 0, "");
+// }
+
+void
+FwPerFibLimits::DoRun ()
+{
+ Simulator::Destroy ();
+
+ NodeContainer nodes;
+ nodes.Create (2);
+
+ PointToPointHelper p2pHelper;
+ p2pHelper.Install (nodes);
+
+ StackHelper ndn;
+ ndn.SetForwardingStrategy ("ns3::ndn::fw::PerFibLimits");
+ ndn.Install (nodes);
+
+ Ptr<Fib> fib = nodes.Get (0)->GetObject<Fib> ();
+ ndn.AddRoute (nodes.Get (0), "/bla", 0, 10);
+
+ Ptr<fib::Entry> entry = fib->Begin ();
+
+ bool ok = entry->GetLimits ().TraceConnect ("CurMaxLimit", "fibEntry.curMax", MakeCallback (PrintTracedValue<double>));
+ NS_TEST_ASSERT_MSG_EQ (ok, true, "");
+
+ ok = entry->GetLimits ().TraceConnect ("Outstanding", "fibEntry.out", MakeCallback (PrintTracedValue<uint32_t>));
+ NS_TEST_ASSERT_MSG_EQ (ok, true, "");
+
+ ok = nodes.Get (0)->GetObject<L3Protocol> ()->GetFace (0)->GetLimits ()->TraceConnect ("CurMaxLimit", "face.curMax", MakeCallback (PrintTracedValue<double>));
+ NS_TEST_ASSERT_MSG_EQ (ok, true, "");
+ ok = nodes.Get (0)->GetObject<L3Protocol> ()->GetFace (0)->GetLimits ()->TraceConnect ("Outstanding", "face.out", MakeCallback (PrintTracedValue<uint32_t>));
+ NS_TEST_ASSERT_MSG_EQ (ok, true, "");
+
+ nodes.Get (0)->GetObject<L3Protocol> ()->GetFace (0)->GetLimits ()->SetMaxLimit (100);
+
+ entry->GetLimits ().SetMaxLimit (100);
+ NS_TEST_ASSERT_MSG_EQ_TOL ((double)entry->GetLimits ().m_curMaxLimit, 100, 0.1, "");
+
+ entry->GetLimits ().DecreaseLimit ();
+ NS_TEST_ASSERT_MSG_EQ_TOL ((double)entry->GetLimits ().m_curMaxLimit, 50, 0.1, "");
+
+ entry = fib->Begin ();
+
+ NS_LOG_DEBUG (entry);
+ Simulator::Schedule (Seconds (0.1), Decay, entry);
+ Simulator::Schedule (Seconds (25.0), Decay, entry);
+ Simulator::Schedule (Seconds (28.0), Decay, entry);
+ Simulator::Schedule (Seconds (40.0), Decay, entry);
+ Simulator::Schedule (Seconds (60.0), Decay, entry);
+ Simulator::Schedule (Seconds (100.0), Decay, entry);
+
+ Simulator::Schedule (Seconds (100.1), &FwPerFibLimits::CheckCurMaxLimit, this, entry, 81.5);
+
+ Simulator::Schedule (Seconds (100.5), &FwPerFibLimits::CheckOutstanding, this, entry, 0);
+ Simulator::Schedule (Seconds (101.0), Test1, entry);
+ Simulator::Schedule (Seconds (101.5), &FwPerFibLimits::CheckOutstanding, this, entry, 1);
+ Simulator::Schedule (Seconds (101.5), &FwPerFibLimits::CheckCurMaxLimit, this, entry, 40.75);
+
+ Simulator::Schedule (Seconds (102.0), Test2, entry);
+ Simulator::Schedule (Seconds (102.5), &FwPerFibLimits::CheckOutstanding, this, entry, 0);
+ Simulator::Schedule (Seconds (102.5), &FwPerFibLimits::CheckCurMaxLimit, this, entry, 41.75);
+
+ // Config::Connect ("/NodeList/*/$ns3::ndn::L3Protocol/FaceList/*/Limits/CurMaxLimit", MakeCallback (PrintTracedValue<double>));
+ // Config::Connect ("/NodeList/*/$ns3::ndn::L3Protocol/FaceList/*/Limits/Outstanding", MakeCallback (PrintTracedValue<uint32_t>));
+
+ AppHelper consumer ("ns3::ndn::ConsumerBatches");
+ consumer.SetPrefix ("/bla");
+ consumer.SetAttribute ("Batches", StringValue ("105 1"));
+ consumer.SetAttribute ("LifeTime", StringValue ("1s"));
+ consumer.Install (nodes.Get (0));
+
+ Simulator::Stop (Seconds (110.0));
+ Simulator::Run ();
+
+ Simulator::Destroy ();
+}
+
+} // namespace ndn
+} // namespace ns3
diff --git a/test/fw-per-fib-limits.h b/test/fw-per-fib-limits.h
new file mode 100644
index 0000000..51bd0c4
--- /dev/null
+++ b/test/fw-per-fib-limits.h
@@ -0,0 +1,52 @@
+/* -*- 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 NDNSIM_TEST_FW_PER_FIB_LIMITS_H
+#define NDNSIM_TEST_FW_PER_FIB_LIMITS_H
+
+#include "ns3/test.h"
+#include "ns3/ptr.h"
+
+namespace ns3 {
+namespace ndn {
+
+class Fib;
+namespace fib { class Entry; }
+
+class FwPerFibLimits : public TestCase
+{
+public:
+ FwPerFibLimits ()
+ : TestCase ("Test for ndn::fw::PerFibLimits")
+ {
+ }
+
+private:
+ virtual void DoRun ();
+
+ void CheckCurMaxLimit (Ptr<fib::Entry> entry, double amount);
+ void CheckOutstanding (Ptr<fib::Entry> entry, uint32_t amount);
+ // void Check2 (Ptr<fib::Entry> entry);
+};
+
+} // namespace ndn
+} // namespace ns3
+
+#endif // NDNSIM_TEST_FW_PER_FIB_LIMITS_H
diff --git a/test/ndnSIM-tests.cc b/test/ndnSIM-tests.cc
index e62dc19..ee02a7a 100644
--- a/test/ndnSIM-tests.cc
+++ b/test/ndnSIM-tests.cc
@@ -24,6 +24,7 @@
#include "ndnSIM-serialization.h"
#include "ndnSIM-pit.h"
#include "ndnSIM-stats-tree.h"
+#include "fw-per-fib-limits.h"
namespace ns3
{
@@ -36,10 +37,11 @@
{
SetDataDir (NS_TEST_SOURCEDIR);
- AddTestCase (new InterestSerializationTest ());
- AddTestCase (new ContentObjectSerializationTest ());
- AddTestCase (new PitTest ());
- AddTestCase (new StatsTreeTest ());
+ // AddTestCase (new InterestSerializationTest ());
+ // AddTestCase (new ContentObjectSerializationTest ());
+ // AddTestCase (new PitTest ());
+ // AddTestCase (new StatsTreeTest ());
+ AddTestCase (new ndn::FwPerFibLimits ());
}
};
diff --git a/utils/ndn-limits.cc b/utils/ndn-limits.cc
new file mode 100644
index 0000000..967c773
--- /dev/null
+++ b/utils/ndn-limits.cc
@@ -0,0 +1,131 @@
+/* -*- 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 "ndn-limits.h"
+
+#include "ns3/log.h"
+#include "ns3/simulator.h"
+
+NS_LOG_COMPONENT_DEFINE ("ndn.Limits");
+
+namespace ns3 {
+namespace ndn {
+
+NS_OBJECT_ENSURE_REGISTERED (Limits);
+
+TypeId
+Limits::GetTypeId ()
+{
+ static TypeId tid = TypeId ("ns3::ndn::Limits")
+ .SetGroupName ("Ndn")
+ .SetParent <Object> ()
+ .AddConstructor <Limits> ()
+
+ .AddTraceSource ("CurMaxLimit",
+ "Current maximum limit",
+ MakeTraceSourceAccessor (&Limits::m_curMaxLimit))
+
+ .AddTraceSource ("Outstanding",
+ "Number of outstanding interests",
+ MakeTraceSourceAccessor (&Limits::m_outstanding))
+ ;
+ return tid;
+}
+
+void
+Limits::SetMaxLimit (uint32_t max)
+{
+ m_maxLimit = max;
+ m_curMaxLimit = max;
+}
+
+
+void
+Limits::DecayCurrentLimit ()
+{
+ if (m_maxLimit == 0) return;
+
+ if (!m_lastDecay.IsZero ())
+ {
+ const double tau = 100.0; // seconds
+ double timeDiff = (Simulator::Now () - m_lastDecay).ToDouble (Time::S);
+
+ NS_LOG_DEBUG ("m_maxLimit - (m_maxLimit - m_curMaxLimit) * exp (-timeDiff / tau)");
+ NS_LOG_DEBUG (m_maxLimit << " - " << " ( " << m_maxLimit << " - " << (double)m_curMaxLimit << " ) " << " * " << " exp (- " << timeDiff << " / " << tau << " ) ");
+
+ m_curMaxLimit = m_maxLimit - (m_maxLimit - m_curMaxLimit) * exp (-timeDiff / tau);
+ }
+
+ m_lastDecay = Simulator::Now ();
+}
+
+void
+Limits::IncreaseLimit ()
+{
+ if (m_maxLimit == 0) return;
+
+ // Additive increase
+ m_curMaxLimit = std::min (1.0 * m_maxLimit,
+ (double)m_curMaxLimit + 1.0 / (double)m_curMaxLimit);
+}
+
+void
+Limits::DecreaseLimit ()
+{
+ if (m_maxLimit == 0) return;
+
+ const double maxDecreaseFrequency = 10.0;
+
+ if (!m_lastDecrease.IsZero () && Simulator::Now () - m_lastDecrease < Seconds (1 / maxDecreaseFrequency))
+ return;
+
+ // Multiplicative decrease... almost
+ m_curMaxLimit = 0.5 * m_curMaxLimit;
+
+ m_lastDecrease = Simulator::Now ();
+}
+
+
+bool
+Limits::IsBelowLimit ()
+{
+ if (m_maxLimit == 0) return true;
+
+ if (m_curMaxLimit - m_outstanding > 1.0)
+ {
+ m_outstanding += 1;
+ return true;
+ }
+ else
+ return false;
+}
+
+void
+Limits::RemoveOutstanding ()
+{
+ if (m_maxLimit == 0) return; //limits are disabled
+
+ NS_LOG_DEBUG (m_outstanding);
+ NS_ASSERT_MSG (m_outstanding >= 1, "Should not be possible, unless we decreasing this number twice somewhere");
+ m_outstanding -= 1;
+}
+
+} // namespace ndn
+} // namespace ns3
diff --git a/utils/ndn-limits.h b/utils/ndn-limits.h
new file mode 100644
index 0000000..b8ca50d
--- /dev/null
+++ b/utils/ndn-limits.h
@@ -0,0 +1,106 @@
+/* -*- 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 _NDN_LIMITS_H_
+#define _NDN_LIMITS_H_
+
+#include "ns3/ptr.h"
+#include "ns3/object.h"
+#include "ns3/nstime.h"
+#include "ns3/traced-value.h"
+
+namespace ns3 {
+namespace ndn {
+
+/**
+ * \ingroup ndn
+ * \brief Structure to manage limits for outstanding interests
+ */
+class Limits :
+ public Object
+{
+public:
+ static TypeId
+ GetTypeId ();
+
+ /**
+ * \brief Constructor
+ * \param prefix smart pointer to the prefix for the FIB entry
+ */
+ Limits ()
+ : m_maxLimit (0)
+ , m_curMaxLimit (0)
+ , m_outstanding (0)
+ { }
+
+ /**
+ * Set per-prefix limit
+ */
+ void
+ SetMaxLimit (uint32_t max);
+
+ /**
+ * Decay current limit (exponential decaying)
+ */
+ void
+ DecayCurrentLimit ();
+
+ /**
+ * Increase current limit (additive increase)
+ */
+ void
+ IncreaseLimit ();
+
+ /**
+ * Decrease current limit (multiplicative decrease)
+ */
+ void
+ DecreaseLimit ();
+
+ ////////////////////////////////////////////////////////////////////////////
+ ////////////////////////////////////////////////////////////////////////////
+ ////////////////////////////////////////////////////////////////////////////
+
+ /**
+ * Check if new interest can be send out, if yes, number of outstanding will be increased
+ */
+ bool
+ IsBelowLimit ();
+
+ /**
+ * Remove outstanding interests
+ */
+ void
+ RemoveOutstanding ();
+
+public:
+ uint32_t m_maxLimit;
+
+ TracedValue< double > m_curMaxLimit;
+ TracedValue< uint32_t > m_outstanding;
+
+ Time m_lastDecrease;
+ Time m_lastDecay;
+};
+
+} // namespace ndn
+} // namespace ns3
+
+#endif // _NDN_LIMITS_H_
diff --git a/wscript b/wscript
index b741e15..39699be 100644
--- a/wscript
+++ b/wscript
@@ -89,11 +89,10 @@
"model/pit/ndn-pit-entry-incoming-face.h",
"model/pit/ndn-pit-entry-outgoing-face.h",
-
-
"model/fw/ndn-forwarding-strategy.h",
"utils/batches.h",
+ "utils/ndn-limits.h",
# "utils/weights-path-stretch-tag.h",
]