Separating dynamic limits into a separate forwarding strategy enhancement
Probabilistic method now treats unknown stats as 0.5
diff --git a/model/fw/dynamic-limits.cc b/model/fw/dynamic-limits.cc
new file mode 100644
index 0000000..f20ff3a
--- /dev/null
+++ b/model/fw/dynamic-limits.cc
@@ -0,0 +1,210 @@
+/* -*- 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 "dynamic-limits.h"
+
+#include "ns3/ndn-l3-protocol.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 "ns3/random-variable.h"
+#include "ns3/double.h"
+
+#include <boost/foreach.hpp>
+#include <boost/lexical_cast.hpp>
+#include <boost/lambda/lambda.hpp>
+#include <boost/lambda/bind.hpp>
+namespace ll = boost::lambda;
+
+NS_LOG_COMPONENT_DEFINE ("ndn.fw.DynamicLimits");
+
+namespace ns3 {
+namespace ndn {
+namespace fw {
+
+NS_OBJECT_ENSURE_REGISTERED (DynamicLimits);
+
+TypeId
+DynamicLimits::GetTypeId (void)
+{
+ static TypeId tid = TypeId ("ns3::ndn::fw::DynamicLimits")
+ .SetGroupName ("Ndn")
+ .SetParent <super> ()
+ .AddConstructor <DynamicLimits> ()
+
+ .AddAttribute ("AnnounceLimits", "Enable limit announcement using scope 0 interests",
+ BooleanValue (false),
+ MakeBooleanAccessor (&DynamicLimits::m_announceLimits),
+ MakeBooleanChecker ())
+
+ ;
+ return tid;
+}
+
+DynamicLimits::DynamicLimits ()
+{
+}
+
+void
+DynamicLimits::DoDispose ()
+{
+ m_announceEvent.Cancel ();
+
+ super::DoDispose ();
+}
+
+void
+DynamicLimits::NotifyNewAggregate ()
+{
+ super::NotifyNewAggregate ();
+
+ if (m_announceLimits)
+ {
+ if (m_pit != 0 && m_fib != 0)
+ {
+ m_announceEvent = Simulator::Schedule (Seconds (1.0),
+ &DynamicLimits::AnnounceLimits, this);
+ }
+ }
+}
+
+void
+DynamicLimits::OnInterest (Ptr<Face> face,
+ Ptr<const InterestHeader> header,
+ Ptr<const Packet> origPacket)
+{
+ if (header->GetScope () != 0)
+ super::OnInterest (face, header, origPacket);
+ else
+ ApplyAnnouncedLimit (face, header);
+}
+
+
+void
+DynamicLimits::AnnounceLimits ()
+{
+ Ptr<L3Protocol> l3 = GetObject<L3Protocol> ();
+ NS_ASSERT (l3 != 0);
+
+ if (l3->GetNFaces () < 2)
+ {
+ m_announceEvent = Simulator::Schedule (Seconds (1.0),
+ &DynamicLimits::AnnounceLimits, this);
+ return;
+ }
+
+ double sumOfWeights = 0;
+ double weightNormalization = 1.0;
+ for (uint32_t faceId = 0; faceId < l3->GetNFaces (); faceId ++)
+ {
+ Ptr<Face> inFace = l3->GetFace (faceId);
+
+ const ndnSIM::LoadStatsFace &stats = GetStatsTree ()["/"].incoming ().find (inFace)->second;
+ double weight = std::min (1.0, stats.GetSatisfiedRatio ().get<0> ());
+ if (weight < 0) weight = 0.5;
+
+ sumOfWeights += weight;
+ }
+ if (sumOfWeights >= 1)
+ {
+ // disable normalization (not necessary)
+ weightNormalization = 1.0;
+ }
+ else
+ {
+ // sumOfWeights /= (l3->GetNFaces ());
+ weightNormalization = 1 / sumOfWeights;
+ }
+
+ for (Ptr<fib::Entry> entry = m_fib->Begin ();
+ entry != m_fib->End ();
+ entry = m_fib->Next (entry))
+ {
+ InterestHeader announceInterest;
+ announceInterest.SetScope (0); // link-local
+
+ uint32_t totalAllowance = 0;
+ for (fib::FaceMetricContainer::type::iterator fibFace = entry->m_faces.begin ();
+ fibFace != entry->m_faces.end ();
+ fibFace ++)
+ {
+ totalAllowance += fibFace->m_face->GetLimits ().GetMaxLimit ();
+ }
+
+ if (totalAllowance == 0)
+ {
+ // don't announce anything, there is no limit
+ continue;
+ }
+
+ for (uint32_t faceId = 0; faceId < l3->GetNFaces (); faceId ++)
+ {
+ Ptr<Face> inFace = l3->GetFace (faceId);
+
+ const ndnSIM::LoadStatsFace &stats = GetStatsTree ()["/"].incoming ().find (inFace)->second;
+ double weight = std::min (1.0, stats.GetSatisfiedRatio ().get<0> ());
+ if (weight < 0) weight = 0.5;
+
+ Ptr<NameComponents> prefixWithLimit = Create<NameComponents> (entry->GetPrefix ());
+ (*prefixWithLimit)
+ ("limit")
+ (static_cast<uint32_t> (std::max (1.0, weightNormalization * weight * totalAllowance)));
+
+ announceInterest.SetName (prefixWithLimit);
+ // lifetime is 0
+
+ Ptr<Packet> pkt = Create<Packet> ();
+ pkt->AddHeader (announceInterest);
+
+ inFace->Send (pkt);
+ }
+ }
+
+ m_announceEvent = Simulator::Schedule (Seconds (1.0),
+ &DynamicLimits::AnnounceLimits, this);
+}
+
+void
+DynamicLimits::ApplyAnnouncedLimit (Ptr<Face> inFace,
+ Ptr<const InterestHeader> header)
+{
+ // Ptr<fib::Entry> fibEntry = m_fib->LongestPrefixMatch (header);
+ // if (fibEntry == 0)
+ // return;
+
+ uint32_t limit = boost::lexical_cast<uint32_t> (header->GetName ().GetLastComponent ());
+ inFace->GetLimits ().SetMaxLimit (limit);
+
+ // if (Simulator::GetContext () == 6 || Simulator::GetContext () == 4)
+ // {
+ // std::cerr << Simulator::Now ().ToDouble (Time::S) << "s from:" << *inFace << " " << *header << std::endl;
+ // std::cerr << header->GetName ().GetLastComponent () << ", " << boost::lexical_cast<uint32_t> (header->GetName ().GetLastComponent ()) << std::endl;
+ // }
+}
+
+
+} // namespace fw
+} // namespace ndn
+} // namespace ns3
diff --git a/model/fw/dynamic-limits.h b/model/fw/dynamic-limits.h
new file mode 100644
index 0000000..d7e3d95
--- /dev/null
+++ b/model/fw/dynamic-limits.h
@@ -0,0 +1,84 @@
+/* -*- 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_DYNAMIC_LIMITS_H
+#define NDNSIM_DYNAMIC_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 DynamicLimits :
+ public FwStats
+{
+private:
+ typedef FwStats super;
+
+public:
+ static TypeId
+ GetTypeId ();
+
+ /**
+ * @brief Default constructor
+ */
+ DynamicLimits ();
+
+ virtual void
+ OnInterest (Ptr<Face> face,
+ Ptr<const InterestHeader> header,
+ Ptr<const Packet> origPacket);
+
+private:
+ void
+ AnnounceLimits ();
+
+ void
+ ApplyAnnouncedLimit (Ptr<Face> inFace,
+ Ptr<const InterestHeader> header);
+
+protected:
+ // from Object
+ virtual void
+ NotifyNewAggregate (); ///< @brief Even when object is aggregated to another Object
+
+ virtual void
+ DoDispose ();
+
+private:
+ bool m_announceLimits;
+
+ EventId m_announceEvent;
+};
+
+
+} // namespace fw
+} // namespace ndn
+} // namespace ns3
+
+#endif // NDNSIM_PER_FIB_LIMITS_H
diff --git a/model/fw/per-fib-limits.cc b/model/fw/per-fib-limits.cc
index 95fa65a..99dd6b5 100644
--- a/model/fw/per-fib-limits.cc
+++ b/model/fw/per-fib-limits.cc
@@ -54,15 +54,15 @@
.SetParent <super> ()
.AddConstructor <PerFibLimits> ()
- .AddAttribute ("AnnounceLimits", "Enable limit announcement using scope 0 interests",
- BooleanValue (false),
- MakeBooleanAccessor (&PerFibLimits::m_announceLimits),
- MakeBooleanChecker ())
-
.AddAttribute ("QueueDropNotifications", "Enable explicit notifications (using nacks) that packet was dropped from queue",
BooleanValue (true),
MakeBooleanAccessor (&PerFibLimits::m_queueDropNotifications),
MakeBooleanChecker ())
+
+ .AddAttribute ("WeightedRobin", "Enable weighted round robin for output queues",
+ BooleanValue (false),
+ MakeBooleanAccessor (&PerFibLimits::m_weightedRoundRobin),
+ MakeBooleanChecker ())
;
return tid;
}
@@ -83,15 +83,6 @@
PerFibLimits::NotifyNewAggregate ()
{
super::NotifyNewAggregate ();
-
- if (m_announceLimits)
- {
- if (m_pit != 0 && m_fib != 0)
- {
- m_announceEvent = Simulator::Schedule (Seconds (1.0),
- &PerFibLimits::AnnounceLimits, this);
- }
- }
}
void
@@ -108,17 +99,6 @@
super::RemoveFace (face);
}
-void
-PerFibLimits::OnInterest (Ptr<Face> face,
- Ptr<const InterestHeader> header,
- Ptr<const Packet> origPacket)
-{
- if (header->GetScope () != 0)
- super::OnInterest (face, header, origPacket);
- else
- ApplyAnnouncedLimit (face, header);
-}
-
bool
PerFibLimits::TrySendOutInterest (Ptr<Face> inFace,
Ptr<Face> outFace,
@@ -138,7 +118,7 @@
if (header->GetInterestLifetime () < Seconds (0.1))
{
- NS_LOG_DEBUG( "??? Why interest lifetime is so short? [" << header->GetInterestLifetime ().ToDouble (Time::S) << "s]");
+ NS_LOG_DEBUG( "Interest lifetime is so short? [" << header->GetInterestLifetime ().ToDouble (Time::S) << "s]");
}
pit::Entry::out_iterator outgoing =
@@ -175,10 +155,15 @@
pitEntry->OffsetLifetime (Seconds (-pitEntry->GetInterest ()->GetInterestLifetime ().ToDouble (Time::S)));
pitEntry->UpdateLifetime (Seconds (0.10));
- // const ndnSIM::LoadStatsFace &stats = GetStatsTree ()[header->GetName ()].incoming ().find (inFace)->second;
- // const ndnSIM::LoadStatsFace &stats = GetStatsTree ()["/"].incoming ().find (inFace)->second;
- // double weight = std::min (1.0, stats.GetSatisfiedRatio ().get<0> ());
- bool enqueued = m_pitQueues[outFace].Enqueue (inFace, pitEntry, 1);
+ double weight = 1.0;
+ if (m_weightedRoundRobin)
+ {
+ // const ndnSIM::LoadStatsFace &stats = GetStatsTree ()[header->GetName ()].incoming ().find (inFace)->second;
+ const ndnSIM::LoadStatsFace &stats = GetStatsTree ()["/"].incoming ().find (inFace)->second;
+ weight = std::min (1.0, stats.GetSatisfiedRatio ().get<0> ());
+ // std::cout << ">>>> stats: " << stats << std::endl;
+ }
+ bool enqueued = m_pitQueues[outFace].Enqueue (inFace, pitEntry, weight);
if (enqueued)
{
@@ -346,107 +331,6 @@
ProcessFromQueue ();
}
-void
-PerFibLimits::AnnounceLimits ()
-{
- Ptr<L3Protocol> l3 = GetObject<L3Protocol> ();
- NS_ASSERT (l3 != 0);
-
- if (l3->GetNFaces () < 2)
- {
- m_announceEvent = Simulator::Schedule (Seconds (1.0),
- &PerFibLimits::AnnounceLimits, this);
- return;
- }
-
- double sumOfWeights = 0;
- double weightNormalization = 1.0;
- for (uint32_t faceId = 0; faceId < l3->GetNFaces (); faceId ++)
- {
- Ptr<Face> inFace = l3->GetFace (faceId);
-
- const ndnSIM::LoadStatsFace &stats = GetStatsTree ()["/"].incoming ().find (inFace)->second;
- double weight = std::min (1.0, stats.GetSatisfiedRatio ().get<0> ());
- if (weight < 0) weight = 0.5;
-
- sumOfWeights += weight;
- }
- if (sumOfWeights >= 1)
- {
- // disable normalization (not necessary)
- weightNormalization = 1.0;
- }
- else
- {
- // sumOfWeights /= (l3->GetNFaces ());
- weightNormalization = 1 / sumOfWeights;
- }
-
- for (Ptr<fib::Entry> entry = m_fib->Begin ();
- entry != m_fib->End ();
- entry = m_fib->Next (entry))
- {
- InterestHeader announceInterest;
- announceInterest.SetScope (0); // link-local
-
- uint32_t totalAllowance = 0;
- for (fib::FaceMetricContainer::type::iterator fibFace = entry->m_faces.begin ();
- fibFace != entry->m_faces.end ();
- fibFace ++)
- {
- totalAllowance += fibFace->m_face->GetLimits ().GetMaxLimit ();
- }
-
- if (totalAllowance == 0)
- {
- // don't announce anything, there is no limit
- continue;
- }
-
- for (uint32_t faceId = 0; faceId < l3->GetNFaces (); faceId ++)
- {
- Ptr<Face> inFace = l3->GetFace (faceId);
-
- const ndnSIM::LoadStatsFace &stats = GetStatsTree ()["/"].incoming ().find (inFace)->second;
- double weight = std::min (1.0, stats.GetSatisfiedRatio ().get<0> ());
- if (weight < 0) weight = 0.5;
-
- Ptr<NameComponents> prefixWithLimit = Create<NameComponents> (entry->GetPrefix ());
- (*prefixWithLimit)
- ("limit")
- (static_cast<uint32_t> (std::max (1.0, weightNormalization * weight * totalAllowance)));
-
- announceInterest.SetName (prefixWithLimit);
- // lifetime is 0
-
- Ptr<Packet> pkt = Create<Packet> ();
- pkt->AddHeader (announceInterest);
-
- inFace->Send (pkt);
- }
- }
-
- m_announceEvent = Simulator::Schedule (Seconds (1.0),
- &PerFibLimits::AnnounceLimits, this);
-}
-
-void
-PerFibLimits::ApplyAnnouncedLimit (Ptr<Face> inFace,
- Ptr<const InterestHeader> header)
-{
- // Ptr<fib::Entry> fibEntry = m_fib->LongestPrefixMatch (header);
- // if (fibEntry == 0)
- // return;
-
- uint32_t limit = boost::lexical_cast<uint32_t> (header->GetName ().GetLastComponent ());
- inFace->GetLimits ().SetMaxLimit (limit);
-
- // if (Simulator::GetContext () == 6 || Simulator::GetContext () == 4)
- // {
- // std::cerr << Simulator::Now ().ToDouble (Time::S) << "s from:" << *inFace << " " << *header << std::endl;
- // std::cerr << header->GetName ().GetLastComponent () << ", " << boost::lexical_cast<uint32_t> (header->GetName ().GetLastComponent ()) << std::endl;
- // }
-}
} // namespace fw
diff --git a/model/fw/per-fib-limits.h b/model/fw/per-fib-limits.h
index b377004..ee2eb2c 100644
--- a/model/fw/per-fib-limits.h
+++ b/model/fw/per-fib-limits.h
@@ -24,7 +24,7 @@
#include "ns3/event-id.h"
-#include "fw-stats.h"
+#include "dynamic-limits.h"
#include "../../utils/ndn-pit-queue.h"
namespace ns3 {
@@ -36,10 +36,10 @@
* \brief Strategy implementing per-FIB entry limits
*/
class PerFibLimits :
- public FwStats
+ public DynamicLimits
{
private:
- typedef FwStats super;
+ typedef DynamicLimits super;
public:
static TypeId
@@ -49,11 +49,6 @@
* @brief Default constructor
*/
PerFibLimits ();
-
- virtual void
- OnInterest (Ptr<Face> face,
- Ptr<const InterestHeader> header,
- Ptr<const Packet> origPacket);
virtual void
WillEraseTimedOutPendingInterest (Ptr<pit::Entry> pitEntry);
@@ -81,13 +76,6 @@
private:
void
ProcessFromQueue ();
-
- void
- AnnounceLimits ();
-
- void
- ApplyAnnouncedLimit (Ptr<Face> inFace,
- Ptr<const InterestHeader> header);
// from Object
virtual void
@@ -100,8 +88,8 @@
typedef std::map< Ptr<Face>, PitQueue > PitQueueMap;
PitQueueMap m_pitQueues; // per-outgoing face pit queue
- bool m_announceLimits;
bool m_queueDropNotifications;
+ bool m_weightedRoundRobin;
EventId m_announceEvent;
};
diff --git a/model/fw/stats-based-randomized-interest-accept.cc b/model/fw/stats-based-randomized-interest-accept.cc
index a159801..ef8374f 100644
--- a/model/fw/stats-based-randomized-interest-accept.cc
+++ b/model/fw/stats-based-randomized-interest-accept.cc
@@ -97,21 +97,23 @@
const ndnSIM::LoadStatsFace &stats = GetStatsTree ()["/"].incoming ().find (inFace)->second;
if (stats.count ().GetStats ().get<0> () >= m_threshold * pitEntry->GetFibEntry ()->GetLimits ().GetMaxLimit ())
- {
- double ratio = std::min (1.0, stats.GetSatisfiedRatio ().get<0> ());
- // NS_ASSERT_MSG (ratio > 0, "If count is a reasonable value, ratio cannot be negative");
- UniformVariable randAccept (0, 1);
- double dice = randAccept.GetValue ();
- if (ratio < 0 || dice < ratio + m_graceAcceptProbability)
- {
- // ok, accepting the interests
- }
- else
- {
- // boo. bad luck
- return false;
- }
- }
+ {
+ double ratio = std::min (1.0, stats.GetSatisfiedRatio ().get<0> ());
+ if (ratio < 0) ratio = 0.5;
+ // NS_ASSERT_MSG (ratio > 0, "If count is a reasonable value, ratio cannot be negative");
+ UniformVariable randAccept (0, 1);
+ double dice = randAccept.GetValue ();
+
+ if (ratio < 0 || dice < ratio + m_graceAcceptProbability)
+ {
+ // ok, accepting the interests
+ }
+ else
+ {
+ // boo. bad luck
+ return false;
+ }
+ }
if (pitEntry->GetFibEntry ()->GetLimits ().IsBelowLimit ())
{
diff --git a/model/fw/stats-based-randomized-interest-accept.h b/model/fw/stats-based-randomized-interest-accept.h
index 4fb833e..84494d7 100644
--- a/model/fw/stats-based-randomized-interest-accept.h
+++ b/model/fw/stats-based-randomized-interest-accept.h
@@ -24,7 +24,7 @@
#include "ns3/event-id.h"
-#include "fw-stats.h"
+#include "dynamic-limits.h"
namespace ns3 {
namespace ndn {
@@ -43,7 +43,7 @@
* (probability is shifted to allow small rate of acceptance (1% by default) of Interests from faces with 0 satisfaction ratio.
*/
class StatsBasedRandomizedInterestAccept :
- public FwStats
+ public DynamicLimits
{
public:
static TypeId
diff --git a/utils/ndn-pit-queue.cc b/utils/ndn-pit-queue.cc
index ca0d755..d3d54b3 100644
--- a/utils/ndn-pit-queue.cc
+++ b/utils/ndn-pit-queue.cc
@@ -35,7 +35,7 @@
namespace ns3 {
namespace ndn {
-const double MIN_WEIGHT = 0.1;
+const double MIN_WEIGHT = 0.01;
PitQueue::PitQueue ()
// : m_maxQueueSize (20)
@@ -74,6 +74,10 @@
queue = itemPair.first;
}
+ else
+ {
+ queue->second->get<1> () = updatedWeight;
+ }
if ((inFace->GetLimits ().GetMaxLimit () == 0 && queue->second->get<0> ().size () > 100) ||
(inFace->GetLimits ().GetMaxLimit () != 0 && queue->second->get<0> ().size () >= 0.5 * inFace->GetLimits ().GetMaxLimit ()))
@@ -91,7 +95,22 @@
}
tag->InsertQueue (queue->second, itemIterator);
+ // if (Simulator::GetContext () == 4)
+ // {
+ // cout << "====== " << Simulator::Now ().ToDouble (Time::S) << "s " << *queue->first << endl;
+ // cout << " " << m_serviceCounter << " / " << queue->second->get<1> () << " / " << queue->second->get<2> () << "\n";
+ // for (PerInFaceQueue::const_iterator somequeue = m_queues.begin ();
+ // somequeue != m_queues.end ();
+ // somequeue ++)
+ // {
+ // if (somequeue == queue) cout << "*";
+ // cout << somequeue->second->get<0> ().size () << " ";
+ // }
+ // cout << endl;
+ // }
+
UpdateWeightedRounds ();
+
return true;
}
@@ -131,7 +150,7 @@
// if (Simulator::GetContext () == 4)
// {
// cout << "====== " << Simulator::Now ().ToDouble (Time::S) << "s " << *queue->first << endl;
- // cout << " " << m_serviceCounter << " / " << queue->second->get<2> () << "\n";
+ // cout << " " << m_serviceCounter << " / " << queue->second->get<1> () << " / " << queue->second->get<2> () << "\n";
// for (PerInFaceQueue::const_iterator somequeue = m_queues.begin ();
// somequeue != m_queues.end ();
// somequeue ++)
@@ -241,7 +260,7 @@
queue != m_queues.end ();
queue ++)
{
- queue->second->get<2> () = static_cast<uint32_t>(queue->second->get<1> () / minWeight);
+ queue->second->get<2> () = static_cast<uint32_t>((queue->second->get<1> () / minWeight) + 0.5);
if (queue->second->get<2> () < 1)
queue->second->get<2> () = 1;
}