A Discrete-Event Network Simulator
API
pie-queue-disc.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2016 NITK Surathkal
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation;
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  *
18  * Authors: Shravya Ks <shravya.ks0@gmail.com>
19  * Smriti Murali <m.smriti.95@gmail.com>
20  * Mohit P. Tahiliani <tahiliani@nitk.edu.in>
21  */
22 
23 /*
24  * PORT NOTE: This code was ported from ns-2.36rc1 (queue/pie.cc).
25  * Most of the comments are also ported from the same.
26  */
27 
28 #include "ns3/log.h"
29 #include "ns3/enum.h"
30 #include "ns3/uinteger.h"
31 #include "ns3/double.h"
32 #include "ns3/simulator.h"
33 #include "ns3/abort.h"
34 #include "pie-queue-disc.h"
35 #include "ns3/drop-tail-queue.h"
36 
37 namespace ns3 {
38 
39 NS_LOG_COMPONENT_DEFINE ("PieQueueDisc");
40 
41 NS_OBJECT_ENSURE_REGISTERED (PieQueueDisc);
42 
44 {
45  static TypeId tid = TypeId ("ns3::PieQueueDisc")
46  .SetParent<QueueDisc> ()
47  .SetGroupName ("TrafficControl")
48  .AddConstructor<PieQueueDisc> ()
49  .AddAttribute ("MeanPktSize",
50  "Average of packet size",
51  UintegerValue (1000),
53  MakeUintegerChecker<uint32_t> ())
54  .AddAttribute ("A",
55  "Value of alpha",
56  DoubleValue (0.125),
58  MakeDoubleChecker<double> ())
59  .AddAttribute ("B",
60  "Value of beta",
61  DoubleValue (1.25),
63  MakeDoubleChecker<double> ())
64  .AddAttribute ("Tupdate",
65  "Time period to calculate drop probability",
66  TimeValue (Seconds (0.03)),
68  MakeTimeChecker ())
69  .AddAttribute ("Supdate",
70  "Start time of the update timer",
71  TimeValue (Seconds (0)),
73  MakeTimeChecker ())
74  .AddAttribute ("MaxSize",
75  "The maximum number of packets accepted by this queue disc",
76  QueueSizeValue (QueueSize ("25p")),
80  .AddAttribute ("DequeueThreshold",
81  "Minimum queue size in bytes before dequeue rate is measured",
82  UintegerValue (10000),
84  MakeUintegerChecker<uint32_t> ())
85  .AddAttribute ("QueueDelayReference",
86  "Desired queue delay",
87  TimeValue (Seconds (0.02)),
89  MakeTimeChecker ())
90  .AddAttribute ("MaxBurstAllowance",
91  "Current max burst allowance in seconds before random drop",
92  TimeValue (Seconds (0.1)),
94  MakeTimeChecker ())
95  ;
96 
97  return tid;
98 }
99 
102 {
103  NS_LOG_FUNCTION (this);
104  m_uv = CreateObject<UniformRandomVariable> ();
106 }
107 
109 {
110  NS_LOG_FUNCTION (this);
111 }
112 
113 void
115 {
116  NS_LOG_FUNCTION (this);
117  m_uv = 0;
120 }
121 
122 Time
124 {
125  NS_LOG_FUNCTION (this);
126  return m_qDelay;
127 }
128 
129 int64_t
131 {
132  NS_LOG_FUNCTION (this << stream);
133  m_uv->SetStream (stream);
134  return 1;
135 }
136 
137 bool
139 {
140  NS_LOG_FUNCTION (this << item);
141 
142  QueueSize nQueued = GetCurrentSize ();
143 
144  if (nQueued + item > GetMaxSize ())
145  {
146  // Drops due to queue limit: reactive
148  return false;
149  }
150  else if (DropEarly (item, nQueued.GetValue ()))
151  {
152  // Early probability drop: proactive
154  return false;
155  }
156 
157  // No drop
158  bool retval = GetInternalQueue (0)->Enqueue (item);
159 
160  // If Queue::Enqueue fails, QueueDisc::DropBeforeEnqueue is called by the
161  // internal queue because QueueDisc::AddInternalQueue sets the trace callback
162 
163  NS_LOG_LOGIC ("\t bytesInQueue " << GetInternalQueue (0)->GetNBytes ());
164  NS_LOG_LOGIC ("\t packetsInQueue " << GetInternalQueue (0)->GetNPackets ());
165 
166  return retval;
167 }
168 
169 void
171 {
172  // Initially queue is empty so variables are initialize to zero except m_dqCount
173  m_inMeasurement = false;
175  m_dropProb = 0;
176  m_avgDqRate = 0.0;
177  m_dqStart = 0;
179  m_qDelayOld = Time (Seconds (0));
180 }
181 
182 bool PieQueueDisc::DropEarly (Ptr<QueueDiscItem> item, uint32_t qSize)
183 {
184  NS_LOG_FUNCTION (this << item << qSize);
185  if (m_burstAllowance.GetSeconds () > 0)
186  {
187  // If there is still burst_allowance left, skip random early drop.
188  return false;
189  }
190 
191  if (m_burstState == NO_BURST)
192  {
195  }
196 
197  double p = m_dropProb;
198 
199  uint32_t packetSize = item->GetSize ();
200 
201  if (GetMaxSize ().GetUnit () == QueueSizeUnit::BYTES)
202  {
203  p = p * packetSize / m_meanPktSize;
204  }
205  bool earlyDrop = true;
206  double u = m_uv->GetValue ();
207 
208  if ((m_qDelayOld.GetSeconds () < (0.5 * m_qDelayRef.GetSeconds ())) && (m_dropProb < 0.2))
209  {
210  return false;
211  }
212  else if (GetMaxSize ().GetUnit () == QueueSizeUnit::BYTES && qSize <= 2 * m_meanPktSize)
213  {
214  return false;
215  }
216  else if (GetMaxSize ().GetUnit () == QueueSizeUnit::PACKETS && qSize <= 2)
217  {
218  return false;
219  }
220 
221  if (u > p)
222  {
223  earlyDrop = false;
224  }
225  if (!earlyDrop)
226  {
227  return false;
228  }
229 
230  return true;
231 }
232 
234 {
235  NS_LOG_FUNCTION (this);
236  Time qDelay;
237  double p = 0.0;
238  bool missingInitFlag = false;
239  if (m_avgDqRate > 0)
240  {
241  qDelay = Time (Seconds (GetInternalQueue (0)->GetNBytes () / m_avgDqRate));
242  }
243  else
244  {
245  qDelay = Time (Seconds (0));
246  missingInitFlag = true;
247  }
248 
249  m_qDelay = qDelay;
250 
251  if (m_burstAllowance.GetSeconds () > 0)
252  {
253  m_dropProb = 0;
254  }
255  else
256  {
257  p = m_a * (qDelay.GetSeconds () - m_qDelayRef.GetSeconds ()) + m_b * (qDelay.GetSeconds () - m_qDelayOld.GetSeconds ());
258  if (m_dropProb < 0.001)
259  {
260  p /= 32;
261  }
262  else if (m_dropProb < 0.01)
263  {
264  p /= 8;
265  }
266  else if (m_dropProb < 0.1)
267  {
268  p /= 2;
269  }
270  else if (m_dropProb < 1)
271  {
272  p /= 0.5;
273  }
274  else if (m_dropProb < 10)
275  {
276  p /= 0.125;
277  }
278  else
279  {
280  p /= 0.03125;
281  }
282  if ((m_dropProb >= 0.1) && (p > 0.02))
283  {
284  p = 0.02;
285  }
286  }
287 
288  p += m_dropProb;
289 
290  // For non-linear drop in prob
291 
292  if (qDelay.GetSeconds () == 0 && m_qDelayOld.GetSeconds () == 0)
293  {
294  p *= 0.98;
295  }
296  else if (qDelay.GetSeconds () > 0.2)
297  {
298  p += 0.02;
299  }
300 
301  m_dropProb = (p > 0) ? p : 0;
303  {
304  m_burstAllowance = Time (Seconds (0));
305  }
306  else
307  {
309  }
310 
311  uint32_t burstResetLimit = static_cast<uint32_t>(BURST_RESET_TIMEOUT / m_tUpdate.GetSeconds ());
312  if ( (qDelay.GetSeconds () < 0.5 * m_qDelayRef.GetSeconds ()) && (m_qDelayOld.GetSeconds () < (0.5 * m_qDelayRef.GetSeconds ())) && (m_dropProb == 0) && !missingInitFlag )
313  {
315  m_avgDqRate = 0.0;
316  }
317  if ( (qDelay.GetSeconds () < 0.5 * m_qDelayRef.GetSeconds ()) && (m_qDelayOld.GetSeconds () < (0.5 * m_qDelayRef.GetSeconds ())) && (m_dropProb == 0) && (m_burstAllowance.GetSeconds () == 0))
318  {
320  {
322  m_burstReset = 0;
323  }
324  else if (m_burstState == IN_BURST)
325  {
326  m_burstReset++;
327  if (m_burstReset > burstResetLimit)
328  {
329  m_burstReset = 0;
331  }
332  }
333  }
334  else if (m_burstState == IN_BURST)
335  {
336  m_burstReset = 0;
337  }
338 
339  m_qDelayOld = qDelay;
341 }
342 
345 {
346  NS_LOG_FUNCTION (this);
347 
348  if (GetInternalQueue (0)->IsEmpty ())
349  {
350  NS_LOG_LOGIC ("Queue empty");
351  return 0;
352  }
353 
354  Ptr<QueueDiscItem> item = GetInternalQueue (0)->Dequeue ();
355  double now = Simulator::Now ().GetSeconds ();
356  uint32_t pktSize = item->GetSize ();
357 
358  // if not in a measurement cycle and the queue has built up to dq_threshold,
359  // start the measurement cycle
360 
361  if ( (GetInternalQueue (0)->GetNBytes () >= m_dqThreshold) && (!m_inMeasurement) )
362  {
363  m_dqStart = now;
364  m_dqCount = 0;
365  m_inMeasurement = true;
366  }
367 
368  if (m_inMeasurement)
369  {
370  m_dqCount += pktSize;
371 
372  // done with a measurement cycle
373  if (m_dqCount >= m_dqThreshold)
374  {
375 
376  double tmp = now - m_dqStart;
377 
378  if (tmp > 0)
379  {
380  if (m_avgDqRate == 0)
381  {
382  m_avgDqRate = m_dqCount / tmp;
383  }
384  else
385  {
386  m_avgDqRate = (0.5 * m_avgDqRate) + (0.5 * (m_dqCount / tmp));
387  }
388  }
389 
390  // restart a measurement cycle if there is enough data
391  if (GetInternalQueue (0)->GetNBytes () > m_dqThreshold)
392  {
393  m_dqStart = now;
394  m_dqCount = 0;
395  m_inMeasurement = true;
396  }
397  else
398  {
399  m_dqCount = 0;
400  m_inMeasurement = false;
401  }
402  }
403  }
404 
405  return item;
406 }
407 
408 bool
410 {
411  NS_LOG_FUNCTION (this);
412  if (GetNQueueDiscClasses () > 0)
413  {
414  NS_LOG_ERROR ("PieQueueDisc cannot have classes");
415  return false;
416  }
417 
418  if (GetNPacketFilters () > 0)
419  {
420  NS_LOG_ERROR ("PieQueueDisc cannot have packet filters");
421  return false;
422  }
423 
424  if (GetNInternalQueues () == 0)
425  {
426  // add a DropTail queue
428  ("MaxSize", QueueSizeValue (GetMaxSize ())));
429  }
430 
431  if (GetNInternalQueues () != 1)
432  {
433  NS_LOG_ERROR ("PieQueueDisc needs 1 internal queue");
434  return false;
435  }
436 
437  return true;
438 }
439 
440 } //namespace ns3
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:102
Time m_tUpdate
Time period after which CalculateP () is called.
uint32_t GetNPackets(void) const
Get the number of packets stored by the queue disc.
Definition: queue-disc.cc:435
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:73
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
void SetStream(int64_t stream)
Specifies the stream number for the RngStream.
Class for representing queue sizes.
Definition: queue-size.h:94
void DropBeforeEnqueue(Ptr< const QueueDiscItem > item, const char *reason)
Perform the actions required when the queue disc is notified of a packet dropped before enqueue...
Definition: queue-disc.cc:721
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
double m_avgDqRate
Time averaged dequeue rate.
Time m_maxBurst
Maximum burst allowed before random early dropping kicks in.
uint32_t GetValue() const
Get the underlying value.
Definition: queue-size.cc:175
double m_a
Parameter to pie controller.
QueueSize GetCurrentSize(void)
Get the current size of the queue disc in bytes, if operating in bytes mode, or packets, otherwise.
Definition: queue-disc.cc:518
double GetSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:355
static constexpr const char * FORCED_DROP
Drops due to queue limit: reactive.
virtual void InitializeParams(void)
Initialize the queue parameters.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:204
uint32_t GetNBytes(void) const
Get the amount of bytes stored by the queue disc.
Definition: queue-disc.cc:442
uint32_t m_burstReset
Used to reset value of burst allowance.
static constexpr const char * UNFORCED_DROP
Early probability drops: proactive.
void(* Time)(Time oldValue, Time newValue)
TracedValue callback signature for Time.
Definition: nstime.h:743
QueueDisc is an abstract base class providing the interface and implementing the operations common to...
Definition: queue-disc.h:181
Implements PIE Active Queue Management discipline.
Time m_qDelayRef
Desired queue delay.
double m_dropProb
Variable used in calculation of drop probability.
uint32_t m_meanPktSize
Average packet size in bytes.
Ptr< const AttributeChecker > MakeTimeChecker(const Time min, const Time max)
Helper to make a Time checker with bounded range.
Definition: time.cc:446
void AddInternalQueue(Ptr< InternalQueue > queue)
Add an internal queue to the tail of the list of queues.
Definition: queue-disc.cc:576
Time GetQueueDelay(void)
Get queue delay.
Ptr< T > CreateObjectWithAttributes(std::string n1="", const AttributeValue &v1=EmptyAttributeValue(), std::string n2="", const AttributeValue &v2=EmptyAttributeValue(), std::string n3="", const AttributeValue &v3=EmptyAttributeValue(), std::string n4="", const AttributeValue &v4=EmptyAttributeValue(), std::string n5="", const AttributeValue &v5=EmptyAttributeValue(), std::string n6="", const AttributeValue &v6=EmptyAttributeValue(), std::string n7="", const AttributeValue &v7=EmptyAttributeValue(), std::string n8="", const AttributeValue &v8=EmptyAttributeValue(), std::string n9="", const AttributeValue &v9=EmptyAttributeValue())
Allocate an Object on the heap and initialize with a set of attributes.
static EventId Schedule(Time const &delay, MEM mem_ptr, OBJ obj)
Schedule an event to expire after delay.
Definition: simulator.h:1389
virtual bool CheckConfig(void)
Check whether the current configuration is correct.
AttributeValue implementation for Time.
Definition: nstime.h:1124
Ptr< InternalQueue > GetInternalQueue(std::size_t i) const
Get the i-th internal queue.
Definition: queue-disc.cc:596
Hold an unsigned integer type.
Definition: uinteger.h:44
Use number of packets for queue size.
Definition: queue-size.h:44
Time m_sUpdate
Start time of the update timer.
uint32_t m_dqThreshold
Minimum queue size in bytes before dequeue rate is measured.
#define BURST_RESET_TIMEOUT
Ptr< const AttributeAccessor > MakeQueueSizeAccessor(T1 a1)
Definition: queue-size.h:221
virtual void DoDispose(void)
Dispose of the object.
Definition: queue-disc.cc:378
Time m_qDelayOld
Old value of queue delay.
double m_dqStart
Start timestamp of current measurement cycle.
bool DropEarly(Ptr< QueueDiscItem > item, uint32_t qSize)
Check if a packet needs to be dropped due to probability drop.
virtual void DoDispose(void)
Dispose of the object.
Introspection did not find any typical Config paths.
Ptr< const AttributeChecker > MakeQueueSizeChecker(void)
Definition: queue-size.cc:29
void CalculateP()
Periodically update the drop probability based on the delay samples: not only the current delay sampl...
static void Remove(const EventId &id)
Remove an event from the event list.
Definition: simulator.cc:280
Every class exported by the ns3 library is enclosed in the ns3 namespace.
std::size_t GetNQueueDiscClasses(void) const
Get the number of queue disc classes.
Definition: queue-disc.cc:661
double GetValue(double min, double max)
Get the next random value, as a double in the specified range .
EventId m_rtrsEvent
Event used to decide the decision of interval of drop probability calculation.
Ptr< const AttributeAccessor > MakeTimeAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method...
Definition: nstime.h:1125
static Time Now(void)
Return the current simulation virtual time.
Definition: simulator.cc:193
Ptr< UniformRandomVariable > m_uv
Rng stream.
NS_LOG_LOGIC("Net device "<< nd<< " is not bridged")
PieQueueDisc()
PieQueueDisc Constructor.
QueueSize GetMaxSize(void) const
Get the maximum size of the queue disc.
Definition: queue-disc.cc:449
QueueSizeUnit GetUnit() const
Get the underlying unit.
Definition: queue-size.cc:169
Ptr< const AttributeAccessor > MakeDoubleAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method...
Definition: double.h:42
virtual Ptr< QueueDiscItem > DoDequeue(void)
This function actually extracts a packet from the queue disc.
QueueDiscSizePolicy
Enumeration of the available policies to handle the queue disc size.
Definition: queue-disc.h:103
int64_t AssignStreams(int64_t stream)
Assign a fixed random variable stream number to the random variables used by this model...
Used by queue discs with single internal queue.
Definition: queue-disc.h:105
Time m_qDelay
Current value of queue delay.
static TypeId GetTypeId(void)
Get the type ID.
std::size_t GetNPacketFilters(void) const
Get the number of packet filters.
Definition: queue-disc.cc:623
BurstStateT m_burstState
Used to determine the current state of burst.
Time Seconds(double value)
Construct a Time in the indicated unit.
Definition: nstime.h:1062
Time m_burstAllowance
Current max burst value in seconds that is allowed before random drops kick in.
bool SetMaxSize(QueueSize size)
Set the maximum size of the queue disc.
Definition: queue-disc.cc:477
virtual ~PieQueueDisc()
PieQueueDisc Destructor.
#define NS_LOG_ERROR(msg)
Use NS_LOG to output a message of level LOG_ERROR.
Definition: log.h:256
static const uint32_t packetSize
virtual bool DoEnqueue(Ptr< QueueDiscItem > item)
This function actually enqueues a packet into the queue disc.
This class can be used to hold variables of floating point type such as &#39;double&#39; or &#39;float&#39;...
Definition: double.h:41
double m_b
Parameter to pie controller.
Ptr< const AttributeAccessor > MakeUintegerAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method...
Definition: uinteger.h:45
Use number of bytes for queue size.
Definition: queue-size.h:45
uint64_t m_dqCount
Number of bytes departed since current measurement cycle starts.
a unique identifier for an interface.
Definition: type-id.h:58
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:915
static const uint64_t DQCOUNT_INVALID
Invalid dqCount value.
bool m_inMeasurement
Indicates whether we are in a measurement cycle.
std::size_t GetNInternalQueues(void) const
Get the number of internal queues.
Definition: queue-disc.cc:603