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 ("Mode",
50  "Determines unit for QueueLimit",
53  MakeEnumChecker (Queue::QUEUE_MODE_BYTES, "QUEUE_MODE_BYTES",
54  Queue::QUEUE_MODE_PACKETS, "QUEUE_MODE_PACKETS"))
55  .AddAttribute ("MeanPktSize",
56  "Average of packet size",
57  UintegerValue (1000),
59  MakeUintegerChecker<uint32_t> ())
60  .AddAttribute ("A",
61  "Value of alpha",
62  DoubleValue (0.125),
64  MakeDoubleChecker<double> ())
65  .AddAttribute ("B",
66  "Value of beta",
67  DoubleValue (1.25),
69  MakeDoubleChecker<double> ())
70  .AddAttribute ("Tupdate",
71  "Time period to calculate drop probability",
72  TimeValue (Seconds (0.03)),
74  MakeTimeChecker ())
75  .AddAttribute ("Supdate",
76  "Start time of the update timer",
77  TimeValue (Seconds (0)),
79  MakeTimeChecker ())
80  .AddAttribute ("QueueLimit",
81  "Queue limit in bytes/packets",
82  UintegerValue (25),
84  MakeUintegerChecker<uint32_t> ())
85  .AddAttribute ("DequeueThreshold",
86  "Minimum queue size in bytes before dequeue rate is measured",
87  UintegerValue (10000),
89  MakeUintegerChecker<uint32_t> ())
90  .AddAttribute ("QueueDelayReference",
91  "Desired queue delay",
92  TimeValue (Seconds (0.02)),
94  MakeTimeChecker ())
95  .AddAttribute ("MaxBurstAllowance",
96  "Current max burst allowance in seconds before random drop",
97  TimeValue (Seconds (0.1)),
99  MakeTimeChecker ())
100  ;
101 
102  return tid;
103 }
104 
106  : QueueDisc ()
107 {
108  NS_LOG_FUNCTION (this);
109  m_uv = CreateObject<UniformRandomVariable> ();
111 }
112 
114 {
115  NS_LOG_FUNCTION (this);
116 }
117 
118 void
120 {
121  NS_LOG_FUNCTION (this);
122  m_uv = 0;
125 }
126 
127 void
129 {
130  NS_LOG_FUNCTION (this << mode);
131  m_mode = mode;
132 }
133 
136 {
137  NS_LOG_FUNCTION (this);
138  return m_mode;
139 }
140 
141 void
143 {
144  NS_LOG_FUNCTION (this << lim);
145  m_queueLimit = lim;
146 }
147 
148 uint32_t
150 {
151  NS_LOG_FUNCTION (this);
153  {
154  return GetInternalQueue (0)->GetNBytes ();
155  }
156  else if (GetMode () == Queue::QUEUE_MODE_PACKETS)
157  {
158  return GetInternalQueue (0)->GetNPackets ();
159  }
160  else
161  {
162  NS_ABORT_MSG ("Unknown PIE mode.");
163  }
164 }
165 
168 {
169  NS_LOG_FUNCTION (this);
170  return m_stats;
171 }
172 
173 Time
175 {
176  NS_LOG_FUNCTION (this);
177  return m_qDelay;
178 }
179 
180 int64_t
182 {
183  NS_LOG_FUNCTION (this << stream);
184  m_uv->SetStream (stream);
185  return 1;
186 }
187 
188 bool
190 {
191  NS_LOG_FUNCTION (this << item);
192 
193  uint32_t nQueued = GetQueueSize ();
194 
195  if ((GetMode () == Queue::QUEUE_MODE_PACKETS && nQueued >= m_queueLimit)
196  || (GetMode () == Queue::QUEUE_MODE_BYTES && nQueued + item->GetPacketSize () > m_queueLimit))
197  {
198  // Drops due to queue limit: reactive
199  Drop (item);
201  return false;
202  }
203  else if (DropEarly (item, nQueued))
204  {
205  // Early probability drop: proactive
206  Drop (item);
208  return false;
209  }
210 
211  // No drop
212  bool retval = GetInternalQueue (0)->Enqueue (item);
213 
214  // If Queue::Enqueue fails, QueueDisc::Drop is called by the internal queue
215  // because QueueDisc::AddInternalQueue sets the drop callback
216 
217  NS_LOG_LOGIC ("\t bytesInQueue " << GetInternalQueue (0)->GetNBytes ());
218  NS_LOG_LOGIC ("\t packetsInQueue " << GetInternalQueue (0)->GetNPackets ());
219 
220  return retval;
221 }
222 
223 void
225 {
226  // Initially queue is empty so variables are initialize to zero except m_dqCount
227  m_inMeasurement = false;
228  m_dqCount = -1;
229  m_dropProb = 0;
230  m_avgDqRate = 0.0;
231  m_dqStart = 0;
233  m_qDelayOld = Time (Seconds (0));
234  m_stats.forcedDrop = 0;
235  m_stats.unforcedDrop = 0;
236 }
237 
238 bool PieQueueDisc::DropEarly (Ptr<QueueDiscItem> item, uint32_t qSize)
239 {
240  NS_LOG_FUNCTION (this << item << qSize);
241  if (m_burstAllowance.GetSeconds () > 0)
242  {
243  // If there is still burst_allowance left, skip random early drop.
244  return false;
245  }
246 
247  if (m_burstState == NO_BURST)
248  {
251  }
252 
253  double p = m_dropProb;
254 
255  uint32_t packetSize = item->GetPacketSize ();
256 
258  {
259  p = p * packetSize / m_meanPktSize;
260  }
261  bool earlyDrop = true;
262  double u = m_uv->GetValue ();
263 
264  if ((m_qDelayOld.GetSeconds () < (0.5 * m_qDelayRef.GetSeconds ())) && (m_dropProb < 0.2))
265  {
266  return false;
267  }
268  else if (GetMode () == Queue::QUEUE_MODE_BYTES && qSize <= 2 * m_meanPktSize)
269  {
270  return false;
271  }
272  else if (GetMode () == Queue::QUEUE_MODE_PACKETS && qSize <= 2)
273  {
274  return false;
275  }
276 
277  if (u > p)
278  {
279  earlyDrop = false;
280  }
281  if (!earlyDrop)
282  {
283  return false;
284  }
285 
286  return true;
287 }
288 
290 {
291  NS_LOG_FUNCTION (this);
292  Time qDelay;
293  double p = 0.0;
294  bool missingInitFlag = false;
295  if (m_avgDqRate > 0)
296  {
297  qDelay = Time (Seconds (GetInternalQueue (0)->GetNBytes () / m_avgDqRate));
298  }
299  else
300  {
301  qDelay = Time (Seconds (0));
302  missingInitFlag = true;
303  }
304 
305  m_qDelay = qDelay;
306 
307  if (m_burstAllowance.GetSeconds () > 0)
308  {
309  m_dropProb = 0;
310  }
311  else
312  {
313  p = m_a * (qDelay.GetSeconds () - m_qDelayRef.GetSeconds ()) + m_b * (qDelay.GetSeconds () - m_qDelayOld.GetSeconds ());
314  if (m_dropProb < 0.001)
315  {
316  p /= 32;
317  }
318  else if (m_dropProb < 0.01)
319  {
320  p /= 8;
321  }
322  else if (m_dropProb < 0.1)
323  {
324  p /= 2;
325  }
326  else if (m_dropProb < 1)
327  {
328  p /= 0.5;
329  }
330  else if (m_dropProb < 10)
331  {
332  p /= 0.125;
333  }
334  else
335  {
336  p /= 0.03125;
337  }
338  if ((m_dropProb >= 0.1) && (p > 0.02))
339  {
340  p = 0.02;
341  }
342  }
343 
344  p += m_dropProb;
345 
346  // For non-linear drop in prob
347 
348  if (qDelay.GetSeconds () == 0 && m_qDelayOld.GetSeconds () == 0)
349  {
350  p *= 0.98;
351  }
352  else if (qDelay.GetSeconds () > 0.2)
353  {
354  p += 0.02;
355  }
356 
357  m_dropProb = (p > 0) ? p : 0;
359  {
360  m_burstAllowance = Time (Seconds (0));
361  }
362  else
363  {
365  }
366 
367  uint32_t burstResetLimit = BURST_RESET_TIMEOUT / m_tUpdate.GetSeconds ();
368  if ( (qDelay.GetSeconds () < 0.5 * m_qDelayRef.GetSeconds ()) && (m_qDelayOld.GetSeconds () < (0.5 * m_qDelayRef.GetSeconds ())) && (m_dropProb == 0) && !missingInitFlag )
369  {
370  m_dqCount = -1;
371  m_avgDqRate = 0.0;
372  }
373  if ( (qDelay.GetSeconds () < 0.5 * m_qDelayRef.GetSeconds ()) && (m_qDelayOld.GetSeconds () < (0.5 * m_qDelayRef.GetSeconds ())) && (m_dropProb == 0) && (m_burstAllowance.GetSeconds () == 0))
374  {
376  {
378  m_burstReset = 0;
379  }
380  else if (m_burstState == IN_BURST)
381  {
382  m_burstReset++;
383  if (m_burstReset > burstResetLimit)
384  {
385  m_burstReset = 0;
387  }
388  }
389  }
390  else if (m_burstState == IN_BURST)
391  {
392  m_burstReset = 0;
393  }
394 
395  m_qDelayOld = qDelay;
397 }
398 
401 {
402  NS_LOG_FUNCTION (this);
403 
404  if (GetInternalQueue (0)->IsEmpty ())
405  {
406  NS_LOG_LOGIC ("Queue empty");
407  return 0;
408  }
409 
410  Ptr<QueueDiscItem> item = StaticCast<QueueDiscItem> (GetInternalQueue (0)->Dequeue ());
411  double now = Simulator::Now ().GetSeconds ();
412  uint32_t pktSize = item->GetPacketSize ();
413 
414  // if not in a measurement cycle and the queue has built up to dq_threshold,
415  // start the measurement cycle
416 
417  if ( (GetInternalQueue (0)->GetNBytes () >= m_dqThreshold) && (!m_inMeasurement) )
418  {
419  m_dqStart = now;
420  m_dqCount = 0;
421  m_inMeasurement = true;
422  }
423 
424  if (m_inMeasurement)
425  {
426  m_dqCount += pktSize;
427 
428  // done with a measurement cycle
429  if (m_dqCount >= m_dqThreshold)
430  {
431 
432  double tmp = now - m_dqStart;
433 
434  if (tmp > 0)
435  {
436  if (m_avgDqRate == 0)
437  {
438  m_avgDqRate = m_dqCount / tmp;
439  }
440  else
441  {
442  m_avgDqRate = (0.5 * m_avgDqRate) + (0.5 * (m_dqCount / tmp));
443  }
444  }
445 
446  // restart a measurement cycle if there is enough data
447  if (GetInternalQueue (0)->GetNBytes () > m_dqThreshold)
448  {
449  m_dqStart = now;
450  m_dqCount = 0;
451  m_inMeasurement = true;
452  }
453  else
454  {
455  m_dqCount = 0;
456  m_inMeasurement = false;
457  }
458  }
459  }
460 
461  return item;
462 }
463 
466 {
467  NS_LOG_FUNCTION (this);
468  if (GetInternalQueue (0)->IsEmpty ())
469  {
470  NS_LOG_LOGIC ("Queue empty");
471  return 0;
472  }
473 
474  Ptr<const QueueDiscItem> item = StaticCast<const QueueDiscItem> (GetInternalQueue (0)->Peek ());
475 
476  NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
477  NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
478 
479  return item;
480 }
481 
482 bool
484 {
485  NS_LOG_FUNCTION (this);
486  if (GetNQueueDiscClasses () > 0)
487  {
488  NS_LOG_ERROR ("PieQueueDisc cannot have classes");
489  return false;
490  }
491 
492  if (GetNPacketFilters () > 0)
493  {
494  NS_LOG_ERROR ("PieQueueDisc cannot have packet filters");
495  return false;
496  }
497 
498  if (GetNInternalQueues () == 0)
499  {
500  // create a DropTail queue
501  Ptr<Queue> queue = CreateObjectWithAttributes<DropTailQueue> ("Mode", EnumValue (m_mode));
503  {
504  queue->SetMaxPackets (m_queueLimit);
505  }
506  else
507  {
508  queue->SetMaxBytes (m_queueLimit);
509  }
510  AddInternalQueue (queue);
511  }
512 
513  if (GetNInternalQueues () != 1)
514  {
515  NS_LOG_ERROR ("PieQueueDisc needs 1 internal queue");
516  return false;
517  }
518 
519  if (GetInternalQueue (0)->GetMode () != m_mode)
520  {
521  NS_LOG_ERROR ("The mode of the provided queue does not match the mode set on the PieQueueDisc");
522  return false;
523  }
524 
525  if ((m_mode == Queue::QUEUE_MODE_PACKETS && GetInternalQueue (0)->GetMaxPackets () < m_queueLimit)
526  || (m_mode == Queue::QUEUE_MODE_BYTES && GetInternalQueue (0)->GetMaxBytes () < m_queueLimit))
527  {
528  NS_LOG_ERROR ("The size of the internal queue is less than the queue disc limit");
529  return false;
530  }
531 
532  return true;
533 }
534 
535 } //namespace ns3
Stats GetStats()
Get PIE statistics after running.
uint32_t m_dqCount
Number of bytes departed since current measurement cycle starts.
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:102
Time m_tUpdate
Time period after which CalculateP () is called.
uint32_t GetNQueueDiscClasses(void) const
Get the number of queue disc classes.
Definition: queue-disc.cc:379
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 this RNG stream.
#define NS_ABORT_MSG(msg)
Unconditional abnormal program termination with a message.
Definition: abort.h:50
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:44
uint32_t unforcedDrop
Early probability drops: proactive.
double m_avgDqRate
Time averaged dequeue rate.
Queue::QueueMode m_mode
Mode (bytes or packets)
Time m_maxBurst
Maximum burst allowed before random early dropping kicks in.
virtual Ptr< const QueueDiscItem > DoPeek(void) const
This function returns a copy of the next packet the queue disc will extract.
Ptr< Queue > GetInternalQueue(uint32_t i) const
Get the i-th internal queue.
Definition: queue-disc.cc:324
double m_a
Parameter to pie controller.
uint32_t GetNBytes(void) const
Get the amount of bytes stored by the queue disc.
Definition: queue-disc.cc:237
Use number of bytes for maximum queue size.
Definition: queue.h:133
Ptr< const AttributeAccessor > MakeEnumAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method...
Definition: enum.h:209
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:201
uint32_t m_burstReset
Used to reset value of burst allowance.
void(* Time)(Time oldValue, Time newValue)
TracedValue callback signature for Time.
Definition: nstime.h:719
QueueDisc is an abstract base class providing the interface and implementing the operations common to...
Definition: queue-disc.h:205
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.
Queue::QueueMode GetMode(void)
Get the encapsulation mode of this queue.
void SetQueueLimit(uint32_t lim)
Set the limit of the queue in bytes or packets.
Ptr< const AttributeChecker > MakeTimeChecker(const Time min, const Time max)
Helper to make a Time checker with bounded range.
Definition: time.cc:446
double GetSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:341
QueueMode
Enumeration of the modes supported in the class.
Definition: queue.h:130
uint32_t GetNInternalQueues(void) const
Get the number of internal queues.
Definition: queue-disc.cc:331
Time GetQueueDelay(void)
Get queue delay.
void Drop(Ptr< QueueItem > item)
Drop a packet.
Definition: queue-disc.cc:411
Hold variables of type enum.
Definition: enum.h:54
static EventId Schedule(Time const &delay, MEM mem_ptr, OBJ obj)
Schedule an event to expire after delay.
Definition: simulator.h:1238
virtual bool CheckConfig(void)
Check whether the current configuration is correct.
uint32_t forcedDrop
Drops due to queue limit: reactive.
AttributeValue implementation for Time.
Definition: nstime.h:957
Hold an unsigned integer type.
Definition: uinteger.h:44
void AddInternalQueue(Ptr< Queue > queue)
Add an internal queue to the tail of the list of queues.
Definition: queue-disc.cc:314
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
virtual void DoDispose(void)
Dispose of the object.
Definition: queue-disc.cc:190
Time m_qDelayOld
Old value of queue delay.
uint32_t GetNPacketFilters(void) const
Get the number of packet filters.
Definition: queue-disc.cc:351
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:252
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.
void SetMode(Queue::QueueMode mode)
Set the operating mode of this queue.
virtual void DoDispose(void)
Dispose of the object.
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:311
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Stats m_stats
PIE statistics.
double GetValue(double min, double max)
Get the next random value, as a double in the specified range .
uint32_t GetQueueSize(void)
Get the current value of the queue in bytes or packets.
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:958
static Time Now(void)
Return the current simulation virtual time.
Definition: simulator.cc:224
Ptr< UniformRandomVariable > m_uv
Rng stream.
PieQueueDisc()
PieQueueDisc Constructor.
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.
int64_t AssignStreams(int64_t stream)
Assign a fixed random variable stream number to the random variables used by this model...
Ptr< const AttributeChecker > MakeEnumChecker(int v1, std::string n1, int v2, std::string n2, int v3, std::string n3, int v4, std::string n4, int v5, std::string n5, int v6, std::string n6, int v7, std::string n7, int v8, std::string n8, int v9, std::string n9, int v10, std::string n10, int v11, std::string n11, int v12, std::string n12, int v13, std::string n13, int v14, std::string n14, int v15, std::string n15, int v16, std::string n16, int v17, std::string n17, int v18, std::string n18, int v19, std::string n19, int v20, std::string n20, int v21, std::string n21, int v22, std::string n22)
Make an EnumChecker pre-configured with a set of allowed values by name.
Definition: enum.cc:184
Time m_qDelay
Current value of queue delay.
static TypeId GetTypeId(void)
Get the type ID.
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:895
Time m_burstAllowance
Current max burst value in seconds that is allowed before random drops kick in.
virtual ~PieQueueDisc()
PieQueueDisc Destructor.
#define NS_LOG_ERROR(msg)
Use NS_LOG to output a message of level LOG_ERROR.
Definition: log.h:220
static const uint32_t packetSize
virtual bool DoEnqueue(Ptr< QueueDiscItem > item)
This function actually enqueues a packet into the queue disc.
Use number of packets for maximum queue size.
Definition: queue.h:132
uint32_t m_queueLimit
Queue limit in bytes / packets.
This class can be used to hold variables of floating point type such as 'double' or 'float'...
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
a unique identifier for an interface.
Definition: type-id.h:58
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:904
uint32_t GetNPackets(void) const
Get the number of packets stored by the queue disc.
Definition: queue-disc.cc:230
bool m_inMeasurement
Indicates whether we are in a measurement cycle.