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/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 ++;
}