A Discrete-Event Network Simulator
API
red-queue-disc.cc
Go to the documentation of this file.
1 // /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright © 2011 Marcos Talau
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  * Author: Marcos Talau (talau@users.sourceforge.net)
19  *
20  * Thanks to: Duy Nguyen<duy@soe.ucsc.edu> by RED efforts in NS3
21  *
22  *
23  * This file incorporates work covered by the following copyright and
24  * permission notice:
25  *
26  * Copyright (c) 1990-1997 Regents of the University of California.
27  * All rights reserved.
28  *
29  * Redistribution and use in source and binary forms, with or without
30  * modification, are permitted provided that the following conditions
31  * are met:
32  * 1. Redistributions of source code must retain the above copyright
33  * notice, this list of conditions and the following disclaimer.
34  * 2. Redistributions in binary form must reproduce the above copyright
35  * notice, this list of conditions and the following disclaimer in the
36  * documentation and/or other materials provided with the distribution.
37  * 3. Neither the name of the University nor of the Laboratory may be used
38  * to endorse or promote products derived from this software without
39  * specific prior written permission.
40  *
41  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44  * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51  * SUCH DAMAGE.
52  */
53 
54 /*
55  * PORT NOTE: This code was ported from ns-2 (queue/red.cc). Almost all
56  * comments have also been ported from NS-2
57  */
58 
59 #include "ns3/log.h"
60 #include "ns3/enum.h"
61 #include "ns3/uinteger.h"
62 #include "ns3/double.h"
63 #include "ns3/simulator.h"
64 #include "ns3/abort.h"
65 #include "red-queue-disc.h"
66 #include "ns3/drop-tail-queue.h"
67 #include "ns3/net-device-queue-interface.h"
68 
69 namespace ns3 {
70 
71 NS_LOG_COMPONENT_DEFINE ("RedQueueDisc");
72 
73 NS_OBJECT_ENSURE_REGISTERED (RedQueueDisc);
74 
76 {
77  static TypeId tid = TypeId ("ns3::RedQueueDisc")
78  .SetParent<QueueDisc> ()
79  .SetGroupName("TrafficControl")
80  .AddConstructor<RedQueueDisc> ()
81  .AddAttribute ("MeanPktSize",
82  "Average of packet size",
83  UintegerValue (500),
85  MakeUintegerChecker<uint32_t> ())
86  .AddAttribute ("IdlePktSize",
87  "Average packet size used during idle times. Used when m_cautions = 3",
88  UintegerValue (0),
90  MakeUintegerChecker<uint32_t> ())
91  .AddAttribute ("Wait",
92  "True for waiting between dropped packets",
93  BooleanValue (true),
96  .AddAttribute ("Gentle",
97  "True to increases dropping probability slowly when average queue exceeds maxthresh",
98  BooleanValue (true),
101  .AddAttribute ("ARED",
102  "True to enable ARED",
103  BooleanValue (false),
106  .AddAttribute ("AdaptMaxP",
107  "True to adapt m_curMaxP",
108  BooleanValue (false),
111  .AddAttribute ("FengAdaptive",
112  "True to enable Feng's Adaptive RED",
113  BooleanValue (false),
116  .AddAttribute ("NLRED",
117  "True to enable Nonlinear RED",
118  BooleanValue (false),
121  .AddAttribute ("MinTh",
122  "Minimum average length threshold in packets/bytes",
123  DoubleValue (5),
125  MakeDoubleChecker<double> ())
126  .AddAttribute ("MaxTh",
127  "Maximum average length threshold in packets/bytes",
128  DoubleValue (15),
130  MakeDoubleChecker<double> ())
131  .AddAttribute ("MaxSize",
132  "The maximum number of packets accepted by this queue disc",
133  QueueSizeValue (QueueSize ("25p")),
137  .AddAttribute ("QW",
138  "Queue weight related to the exponential weighted moving average (EWMA)",
139  DoubleValue (0.002),
141  MakeDoubleChecker <double> ())
142  .AddAttribute ("LInterm",
143  "The maximum probability of dropping a packet",
144  DoubleValue (50),
146  MakeDoubleChecker <double> ())
147  .AddAttribute ("TargetDelay",
148  "Target average queuing delay in ARED",
149  TimeValue (Seconds (0.005)),
151  MakeTimeChecker ())
152  .AddAttribute ("Interval",
153  "Time interval to update m_curMaxP",
154  TimeValue (Seconds (0.5)),
156  MakeTimeChecker ())
157  .AddAttribute ("Top",
158  "Upper bound for m_curMaxP in ARED",
159  DoubleValue (0.5),
161  MakeDoubleChecker <double> (0, 1))
162  .AddAttribute ("Bottom",
163  "Lower bound for m_curMaxP in ARED",
164  DoubleValue (0.0),
166  MakeDoubleChecker <double> (0, 1))
167  .AddAttribute ("Alpha",
168  "Increment parameter for m_curMaxP in ARED",
169  DoubleValue (0.01),
171  MakeDoubleChecker <double> (0, 1))
172  .AddAttribute ("Beta",
173  "Decrement parameter for m_curMaxP in ARED",
174  DoubleValue (0.9),
176  MakeDoubleChecker <double> (0, 1))
177  .AddAttribute ("FengAlpha",
178  "Decrement parameter for m_curMaxP in Feng's Adaptive RED",
179  DoubleValue (3.0),
181  MakeDoubleChecker <double> ())
182  .AddAttribute ("FengBeta",
183  "Increment parameter for m_curMaxP in Feng's Adaptive RED",
184  DoubleValue (2.0),
186  MakeDoubleChecker <double> ())
187  .AddAttribute ("LastSet",
188  "Store the last time m_curMaxP was updated",
189  TimeValue (Seconds (0.0)),
191  MakeTimeChecker ())
192  .AddAttribute ("Rtt",
193  "Round Trip Time to be considered while automatically setting m_bottom",
194  TimeValue (Seconds (0.1)),
196  MakeTimeChecker ())
197  .AddAttribute ("Ns1Compat",
198  "NS-1 compatibility",
199  BooleanValue (false),
202  .AddAttribute ("LinkBandwidth",
203  "The RED link bandwidth",
204  DataRateValue (DataRate ("1.5Mbps")),
207  .AddAttribute ("LinkDelay",
208  "The RED link delay",
209  TimeValue (MilliSeconds (20)),
211  MakeTimeChecker ())
212  .AddAttribute ("UseEcn",
213  "True to use ECN (packets are marked instead of being dropped)",
214  BooleanValue (false),
217  .AddAttribute ("UseHardDrop",
218  "True to always drop packets above max threshold",
219  BooleanValue (true),
222  ;
223 
224  return tid;
225 }
226 
229 {
230  NS_LOG_FUNCTION (this);
231  m_uv = CreateObject<UniformRandomVariable> ();
232 }
233 
235 {
236  NS_LOG_FUNCTION (this);
237 }
238 
239 void
241 {
242  NS_LOG_FUNCTION (this);
243  m_uv = 0;
245 }
246 
247 void
249 {
250  NS_LOG_FUNCTION (this << alpha);
251  m_alpha = alpha;
252 
253  if (m_alpha > 0.01)
254  {
255  NS_LOG_WARN ("Alpha value is above the recommended bound!");
256  }
257 }
258 
259 double
261 {
262  NS_LOG_FUNCTION (this);
263  return m_alpha;
264 }
265 
266 void
268 {
269  NS_LOG_FUNCTION (this << beta);
270  m_beta = beta;
271 
272  if (m_beta < 0.83)
273  {
274  NS_LOG_WARN ("Beta value is below the recommended bound!");
275  }
276 }
277 
278 double
280 {
281  NS_LOG_FUNCTION (this);
282  return m_beta;
283 }
284 
285 void
287 {
288  NS_LOG_FUNCTION (this << a);
289  m_a = a;
290 
291  if (m_a != 3)
292  {
293  NS_LOG_WARN ("Alpha value does not follow the recommendations!");
294  }
295 }
296 
297 double
299 {
300  NS_LOG_FUNCTION (this);
301  return m_a;
302 }
303 
304 void
306 {
307  NS_LOG_FUNCTION (this << b);
308  m_b = b;
309 
310  if (m_b != 2)
311  {
312  NS_LOG_WARN ("Beta value does not follow the recommendations!");
313  }
314 }
315 
316 double
318 {
319  NS_LOG_FUNCTION (this);
320  return m_b;
321 }
322 
323 void
324 RedQueueDisc::SetTh (double minTh, double maxTh)
325 {
326  NS_LOG_FUNCTION (this << minTh << maxTh);
327  NS_ASSERT (minTh <= maxTh);
328  m_minTh = minTh;
329  m_maxTh = maxTh;
330 }
331 
332 int64_t
334 {
335  NS_LOG_FUNCTION (this << stream);
336  m_uv->SetStream (stream);
337  return 1;
338 }
339 
340 bool
342 {
343  NS_LOG_FUNCTION (this << item);
344 
345  uint32_t nQueued = GetInternalQueue (0)->GetCurrentSize ().GetValue ();
346 
347  // simulate number of packets arrival during idle period
348  uint32_t m = 0;
349 
350  if (m_idle == 1)
351  {
352  NS_LOG_DEBUG ("RED Queue Disc is idle.");
353  Time now = Simulator::Now ();
354 
355  if (m_cautious == 3)
356  {
357  double ptc = m_ptc * m_meanPktSize / m_idlePktSize;
358  m = uint32_t (ptc * (now - m_idleTime).GetSeconds ());
359  }
360  else
361  {
362  m = uint32_t (m_ptc * (now - m_idleTime).GetSeconds ());
363  }
364 
365  m_idle = 0;
366  }
367 
368  m_qAvg = Estimator (nQueued, m + 1, m_qAvg, m_qW);
369 
370  NS_LOG_DEBUG ("\t bytesInQueue " << GetInternalQueue (0)->GetNBytes () << "\tQavg " << m_qAvg);
371  NS_LOG_DEBUG ("\t packetsInQueue " << GetInternalQueue (0)->GetNPackets () << "\tQavg " << m_qAvg);
372 
373  m_count++;
374  m_countBytes += item->GetSize ();
375 
376  uint32_t dropType = DTYPE_NONE;
377  if (m_qAvg >= m_minTh && nQueued > 1)
378  {
379  if ((!m_isGentle && m_qAvg >= m_maxTh) ||
380  (m_isGentle && m_qAvg >= 2 * m_maxTh))
381  {
382  NS_LOG_DEBUG ("adding DROP FORCED MARK");
383  dropType = DTYPE_FORCED;
384  }
385  else if (m_old == 0)
386  {
387  /*
388  * The average queue size has just crossed the
389  * threshold from below to above m_minTh, or
390  * from above m_minTh with an empty queue to
391  * above m_minTh with a nonempty queue.
392  */
393  m_count = 1;
394  m_countBytes = item->GetSize ();
395  m_old = 1;
396  }
397  else if (DropEarly (item, nQueued))
398  {
399  NS_LOG_LOGIC ("DropEarly returns 1");
400  dropType = DTYPE_UNFORCED;
401  }
402  }
403  else
404  {
405  // No packets are being dropped
406  m_vProb = 0.0;
407  m_old = 0;
408  }
409 
410  if (dropType == DTYPE_UNFORCED)
411  {
412  if (!m_useEcn || !Mark (item, UNFORCED_MARK))
413  {
414  NS_LOG_DEBUG ("\t Dropping due to Prob Mark " << m_qAvg);
416  return false;
417  }
418  NS_LOG_DEBUG ("\t Marking due to Prob Mark " << m_qAvg);
419  }
420  else if (dropType == DTYPE_FORCED)
421  {
422  if (m_useHardDrop || !m_useEcn || !Mark (item, FORCED_MARK))
423  {
424  NS_LOG_DEBUG ("\t Dropping due to Hard Mark " << m_qAvg);
426  if (m_isNs1Compat)
427  {
428  m_count = 0;
429  m_countBytes = 0;
430  }
431  return false;
432  }
433  NS_LOG_DEBUG ("\t Marking due to Hard Mark " << m_qAvg);
434  }
435 
436  bool retval = GetInternalQueue (0)->Enqueue (item);
437 
438  // If Queue::Enqueue fails, QueueDisc::DropBeforeEnqueue is called by the
439  // internal queue because QueueDisc::AddInternalQueue sets the trace callback
440 
441  NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
442  NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
443 
444  return retval;
445 }
446 
447 /*
448  * Note: if the link bandwidth changes in the course of the
449  * simulation, the bandwidth-dependent RED parameters do not change.
450  * This should be fixed, but it would require some extra parameters,
451  * and didn't seem worth the trouble...
452  */
453 void
455 {
456  NS_LOG_FUNCTION (this);
457  NS_LOG_INFO ("Initializing RED params.");
458 
459  m_cautious = 0;
461 
462  if (m_isARED)
463  {
464  // Set m_minTh, m_maxTh and m_qW to zero for automatic setting
465  m_minTh = 0;
466  m_maxTh = 0;
467  m_qW = 0;
468 
469  // Turn on m_isAdaptMaxP to adapt m_curMaxP
470  m_isAdaptMaxP = true;
471  }
472 
473  if (m_isFengAdaptive)
474  {
475  // Initialize m_fengStatus
477  }
478 
479  if (m_minTh == 0 && m_maxTh == 0)
480  {
481  m_minTh = 5.0;
482 
483  // set m_minTh to max(m_minTh, targetqueue/2.0) [Ref: http://www.icir.org/floyd/papers/adaptiveRed.pdf]
484  double targetqueue = m_targetDelay.GetSeconds() * m_ptc;
485 
486  if (m_minTh < targetqueue / 2.0 )
487  {
488  m_minTh = targetqueue / 2.0;
489  }
490  if (GetMaxSize ().GetUnit () == QueueSizeUnit::BYTES)
491  {
493  }
494 
495  // set m_maxTh to three times m_minTh [Ref: http://www.icir.org/floyd/papers/adaptiveRed.pdf]
496  m_maxTh = 3 * m_minTh;
497  }
498 
500 
501  m_qAvg = 0.0;
502  m_count = 0;
503  m_countBytes = 0;
504  m_old = 0;
505  m_idle = 1;
506 
507  double th_diff = (m_maxTh - m_minTh);
508  if (th_diff == 0)
509  {
510  th_diff = 1.0;
511  }
512  m_vA = 1.0 / th_diff;
513  m_curMaxP = 1.0 / m_lInterm;
514  m_vB = -m_minTh / th_diff;
515 
516  if (m_isGentle)
517  {
518  m_vC = (1.0 - m_curMaxP) / m_maxTh;
519  m_vD = 2.0 * m_curMaxP - 1.0;
520  }
521  m_idleTime = NanoSeconds (0);
522 
523 /*
524  * If m_qW=0, set it to a reasonable value of 1-exp(-1/C)
525  * This corresponds to choosing m_qW to be of that value for
526  * which the packet time constant -1/ln(1-m)qW) per default RTT
527  * of 100ms is an order of magnitude more than the link capacity, C.
528  *
529  * If m_qW=-1, then the queue weight is set to be a function of
530  * the bandwidth and the link propagation delay. In particular,
531  * the default RTT is assumed to be three times the link delay and
532  * transmission delay, if this gives a default RTT greater than 100 ms.
533  *
534  * If m_qW=-2, set it to a reasonable value of 1-exp(-10/C).
535  */
536  if (m_qW == 0.0)
537  {
538  m_qW = 1.0 - std::exp (-1.0 / m_ptc);
539  }
540  else if (m_qW == -1.0)
541  {
542  double rtt = 3.0 * (m_linkDelay.GetSeconds () + 1.0 / m_ptc);
543 
544  if (rtt < 0.1)
545  {
546  rtt = 0.1;
547  }
548  m_qW = 1.0 - std::exp (-1.0 / (10 * rtt * m_ptc));
549  }
550  else if (m_qW == -2.0)
551  {
552  m_qW = 1.0 - std::exp (-10.0 / m_ptc);
553  }
554 
555  if (m_bottom == 0)
556  {
557  m_bottom = 0.01;
558  // Set bottom to at most 1/W, where W is the delay-bandwidth
559  // product in packets for a connection.
560  // So W = m_linkBandwidth.GetBitRate () / (8.0 * m_meanPktSize * m_rtt.GetSeconds())
561  double bottom1 = (8.0 * m_meanPktSize * m_rtt.GetSeconds()) / m_linkBandwidth.GetBitRate();
562  if (bottom1 < m_bottom)
563  {
564  m_bottom = bottom1;
565  }
566  }
567 
568  NS_LOG_DEBUG ("\tm_delay " << m_linkDelay.GetSeconds () << "; m_isWait "
569  << m_isWait << "; m_qW " << m_qW << "; m_ptc " << m_ptc
570  << "; m_minTh " << m_minTh << "; m_maxTh " << m_maxTh
571  << "; m_isGentle " << m_isGentle << "; th_diff " << th_diff
572  << "; lInterm " << m_lInterm << "; va " << m_vA << "; cur_max_p "
573  << m_curMaxP << "; v_b " << m_vB << "; m_vC "
574  << m_vC << "; m_vD " << m_vD);
575 }
576 
577 // Updating m_curMaxP, following the pseudocode
578 // from: A Self-Configuring RED Gateway, INFOCOMM '99.
579 // They recommend m_a = 3, and m_b = 2.
580 void
582 {
583  NS_LOG_FUNCTION (this << newAve);
584 
585  if (m_minTh < newAve && newAve < m_maxTh)
586  {
588  }
589  else if (newAve < m_minTh && m_fengStatus != Below)
590  {
592  m_curMaxP = m_curMaxP / m_a;
593  }
594  else if (newAve > m_maxTh && m_fengStatus != Above)
595  {
597  m_curMaxP = m_curMaxP * m_b;
598  }
599 }
600 
601 // Update m_curMaxP to keep the average queue length within the target range.
602 void
604 {
605  NS_LOG_FUNCTION (this << newAve);
606 
607  Time now = Simulator::Now ();
608  double m_part = 0.4 * (m_maxTh - m_minTh);
609  // AIMD rule to keep target Q~1/2(m_minTh + m_maxTh)
610  if (newAve < m_minTh + m_part && m_curMaxP > m_bottom)
611  {
612  // we should increase the average queue size, so decrease m_curMaxP
614  m_lastSet = now;
615  }
616  else if (newAve > m_maxTh - m_part && m_top > m_curMaxP)
617  {
618  // we should decrease the average queue size, so increase m_curMaxP
619  double alpha = m_alpha;
620  if (alpha > 0.25 * m_curMaxP)
621  {
622  alpha = 0.25 * m_curMaxP;
623  }
625  m_lastSet = now;
626  }
627 }
628 
629 // Compute the average queue size
630 double
631 RedQueueDisc::Estimator (uint32_t nQueued, uint32_t m, double qAvg, double qW)
632 {
633  NS_LOG_FUNCTION (this << nQueued << m << qAvg << qW);
634 
635  double newAve = qAvg * std::pow (1.0 - qW, m);
636  newAve += qW * nQueued;
637 
638  Time now = Simulator::Now ();
639  if (m_isAdaptMaxP && now > m_lastSet + m_interval)
640  {
641  UpdateMaxP (newAve);
642  }
643  else if (m_isFengAdaptive)
644  {
645  UpdateMaxPFeng (newAve); // Update m_curMaxP in MIMD fashion.
646  }
647 
648  return newAve;
649 }
650 
651 // Check if packet p needs to be dropped due to probability mark
652 uint32_t
654 {
655  NS_LOG_FUNCTION (this << item << qSize);
656 
657  double prob1 = CalculatePNew ();
658  m_vProb = ModifyP (prob1, item->GetSize ());
659 
660  // Drop probability is computed, pick random number and act
661  if (m_cautious == 1)
662  {
663  /*
664  * Don't drop/mark if the instantaneous queue is much below the average.
665  * For experimental purposes only.
666  * pkts: the number of packets arriving in 50 ms
667  */
668  double pkts = m_ptc * 0.05;
669  double fraction = std::pow ((1 - m_qW), pkts);
670 
671  if ((double) qSize < fraction * m_qAvg)
672  {
673  // Queue could have been empty for 0.05 seconds
674  return 0;
675  }
676  }
677 
678  double u = m_uv->GetValue ();
679 
680  if (m_cautious == 2)
681  {
682  /*
683  * Decrease the drop probability if the instantaneous
684  * queue is much below the average.
685  * For experimental purposes only.
686  * pkts: the number of packets arriving in 50 ms
687  */
688  double pkts = m_ptc * 0.05;
689  double fraction = std::pow ((1 - m_qW), pkts);
690  double ratio = qSize / (fraction * m_qAvg);
691 
692  if (ratio < 1.0)
693  {
694  u *= 1.0 / ratio;
695  }
696  }
697 
698  if (u <= m_vProb)
699  {
700  NS_LOG_LOGIC ("u <= m_vProb; u " << u << "; m_vProb " << m_vProb);
701 
702  // DROP or MARK
703  m_count = 0;
704  m_countBytes = 0;
706 
707  return 1; // drop
708  }
709 
710  return 0; // no drop/mark
711 }
712 
713 // Returns a probability using these function parameters for the DropEarly function
714 double
716 {
717  NS_LOG_FUNCTION (this);
718  double p;
719 
720  if (m_isGentle && m_qAvg >= m_maxTh)
721  {
722  // p ranges from m_curMaxP to 1 as the average queue
723  // size ranges from m_maxTh to twice m_maxTh
724  p = m_vC * m_qAvg + m_vD;
725  }
726  else if (!m_isGentle && m_qAvg >= m_maxTh)
727  {
728  /*
729  * OLD: p continues to range linearly above m_curMaxP as
730  * the average queue size ranges above m_maxTh.
731  * NEW: p is set to 1.0
732  */
733  p = 1.0;
734  }
735  else
736  {
737  /*
738  * p ranges from 0 to m_curMaxP as the average queue size ranges from
739  * m_minTh to m_maxTh
740  */
741  p = m_vA * m_qAvg + m_vB;
742 
743  if (m_isNonlinear)
744  {
745  p *= p * 1.5;
746  }
747 
748  p *= m_curMaxP;
749  }
750 
751  if (p > 1.0)
752  {
753  p = 1.0;
754  }
755 
756  return p;
757 }
758 
759 // Returns a probability using these function parameters for the DropEarly function
760 double
761 RedQueueDisc::ModifyP (double p, uint32_t size)
762 {
763  NS_LOG_FUNCTION (this << p << size);
764  double count1 = (double) m_count;
765 
767  {
768  count1 = (double) (m_countBytes / m_meanPktSize);
769  }
770 
771  if (m_isWait)
772  {
773  if (count1 * p < 1.0)
774  {
775  p = 0.0;
776  }
777  else if (count1 * p < 2.0)
778  {
779  p /= (2.0 - count1 * p);
780  }
781  else
782  {
783  p = 1.0;
784  }
785  }
786  else
787  {
788  if (count1 * p < 1.0)
789  {
790  p /= (1.0 - count1 * p);
791  }
792  else
793  {
794  p = 1.0;
795  }
796  }
797 
798  if ((GetMaxSize ().GetUnit () == QueueSizeUnit::BYTES) && (p < 1.0))
799  {
800  p = (p * size) / m_meanPktSize;
801  }
802 
803  if (p > 1.0)
804  {
805  p = 1.0;
806  }
807 
808  return p;
809 }
810 
813 {
814  NS_LOG_FUNCTION (this);
815 
816  if (GetInternalQueue (0)->IsEmpty ())
817  {
818  NS_LOG_LOGIC ("Queue empty");
819  m_idle = 1;
821 
822  return 0;
823  }
824  else
825  {
826  m_idle = 0;
827  Ptr<QueueDiscItem> item = GetInternalQueue (0)->Dequeue ();
828 
829  NS_LOG_LOGIC ("Popped " << item);
830 
831  NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
832  NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
833 
834  return item;
835  }
836 }
837 
840 {
841  NS_LOG_FUNCTION (this);
842  if (GetInternalQueue (0)->IsEmpty ())
843  {
844  NS_LOG_LOGIC ("Queue empty");
845  return 0;
846  }
847 
848  Ptr<const QueueDiscItem> item = GetInternalQueue (0)->Peek ();
849 
850  NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
851  NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
852 
853  return item;
854 }
855 
856 bool
858 {
859  NS_LOG_FUNCTION (this);
860  if (GetNQueueDiscClasses () > 0)
861  {
862  NS_LOG_ERROR ("RedQueueDisc cannot have classes");
863  return false;
864  }
865 
866  if (GetNPacketFilters () > 0)
867  {
868  NS_LOG_ERROR ("RedQueueDisc cannot have packet filters");
869  return false;
870  }
871 
872  if (GetNInternalQueues () == 0)
873  {
874  // add a DropTail queue
876  ("MaxSize", QueueSizeValue (GetMaxSize ())));
877  }
878 
879  if (GetNInternalQueues () != 1)
880  {
881  NS_LOG_ERROR ("RedQueueDisc needs 1 internal queue");
882  return false;
883  }
884 
886  {
887  NS_LOG_ERROR ("m_isAdaptMaxP and m_isFengAdaptive cannot be simultaneously true");
888  }
889 
890  return true;
891 }
892 
893 } // namespace ns3
bool m_isGentle
True to increase dropping prob.
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:102
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.
double m_beta
Decrement parameter for m_curMaxP in ARED.
AttributeValue implementation for Boolean.
Definition: boolean.h:36
uint32_t m_count
Number of packets since last random number generation.
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:714
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
bool m_isARED
True to enable Adaptive RED.
void SetTh(double minTh, double maxTh)
Set the thresh limits of RED.
virtual bool DoEnqueue(Ptr< QueueDiscItem > item)
This function actually enqueues a packet into the queue disc.
std::size_t GetNQueueDiscClasses(void) const
Get the number of queue disc classes.
Definition: queue-disc.cc:654
uint32_t GetNBytes(void) const
Get the amount of bytes stored by the queue disc.
Definition: queue-disc.cc:448
double GetFengAdaptiveA(void)
Get the alpha value to adapt m_curMaxP in Feng&#39;s Adaptive RED.
double m_qAvg
Average queue length.
bool Mark(Ptr< QueueDiscItem > item, const char *reason)
Marks the given packet and, if successful, updates the counters associated with the given reason...
Definition: queue-disc.cc:803
Time m_linkDelay
Link delay.
Ptr< const AttributeAccessor > MakeBooleanAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method...
Definition: boolean.h:84
void SetAredBeta(double beta)
Set the beta value to adapt m_curMaxP.
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file...
Definition: assert.h:67
uint32_t m_idle
0/1 idle status
FengStatus m_fengStatus
For use in Feng&#39;s Adaptive RED.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:202
Time MilliSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition: nstime.h:1015
QueueSizeUnit GetUnit() const
Get the underlying unit.
Definition: queue-size.cc:169
double m_vD
2.0 * m_curMaxP - 1.0 - used in "gentle" mode
void SetFengAdaptiveB(double b)
Set the beta value to adapt m_curMaxP in Feng&#39;s Adaptive RED.
#define NS_LOG_INFO(msg)
Use NS_LOG to output a message of level LOG_INFO.
Definition: log.h:278
double m_vC
(1.0 - m_curMaxP) / m_maxTh - used in "gentle" mode
bool m_useHardDrop
True if packets are always dropped above max threshold.
double m_qW
Queue weight given to cur queue size sample.
static constexpr const char * FORCED_MARK
Forced marks, m_qAvg > m_maxTh.
QueueDisc is an abstract base class providing the interface and implementing the operations common to...
Definition: queue-disc.h:182
A RED packet queue disc.
double m_b
Increment parameter for m_curMaxP in Feng&#39;s Adaptive RED.
static constexpr const char * FORCED_DROP
Forced drops, m_qAvg > m_maxTh.
int64_t AssignStreams(int64_t stream)
Assign a fixed random variable stream number to the random variables used by this model...
double GetAredAlpha(void)
Get the alpha value to adapt m_curMaxP.
Time m_rtt
Rtt to be considered while automatically setting m_bottom in ARED.
static constexpr const char * UNFORCED_DROP
Early probability drops.
double m_alpha
Increment parameter for m_curMaxP in ARED.
Time m_lastSet
Last time m_curMaxP was updated.
bool m_isAdaptMaxP
True to adapt m_curMaxP.
Ptr< const AttributeChecker > MakeDataRateChecker(void)
Definition: data-rate.cc:30
Ptr< const AttributeChecker > MakeTimeChecker(const Time min, const Time max)
Helper to make a Time checker with bounded range.
Definition: time.cc:446
static TypeId GetTypeId(void)
Get the type ID.
Class for representing data rates.
Definition: data-rate.h:88
double m_curMaxP
Current max_p.
Ptr< InternalQueue > GetInternalQueue(std::size_t i) const
Get the i-th internal queue.
Definition: queue-disc.cc:589
double GetSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:355
void AddInternalQueue(Ptr< InternalQueue > queue)
Add an internal queue to the tail of the list of queues.
Definition: queue-disc.cc:569
Time m_idleTime
Start of current idle period.
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.
AttributeValue implementation for Time.
Definition: nstime.h:1069
double GetFengAdaptiveB(void)
Get the beta value to adapt m_curMaxP in Feng&#39;s Adaptive RED.
Time NanoSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition: nstime.h:1031
virtual bool CheckConfig(void)
Check whether the current configuration is correct.
Hold an unsigned integer type.
Definition: uinteger.h:44
virtual void InitializeParams(void)
Initialize the queue parameters.
uint32_t m_cautious
0 for default RED 1 experimental (see red-queue-disc.cc) 2 experimental (see red-queue-disc.cc) 3 use Idle packet size in the ptc
Ptr< UniformRandomVariable > m_uv
rng stream
std::size_t GetNPacketFilters(void) const
Get the number of packet filters.
Definition: queue-disc.cc:616
Ptr< const AttributeAccessor > MakeQueueSizeAccessor(T1 a1)
Definition: queue-size.h:221
double m_vB
-m_minTh / (m_maxTh - m_minTh)
virtual void DoDispose(void)
Dispose of the object.
Definition: queue-disc.cc:382
bool m_isNonlinear
True to enable Nonlinear RED.
Ptr< const AttributeAccessor > MakeDataRateAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method...
Definition: data-rate.h:242
bool m_useEcn
True if ECN is used (packets are marked instead of being dropped)
double m_minTh
Minimum threshold for m_qAvg (bytes or packets)
virtual Ptr< const QueueDiscItem > DoPeek(void)
Return a copy of the next packet the queue disc will extract.
uint32_t m_idlePktSize
Avg pkt size used during idle times.
Introspection did not find any typical Config paths.
Ptr< const AttributeChecker > MakeQueueSizeChecker(void)
Definition: queue-size.cc:29
std::size_t GetNInternalQueues(void) const
Get the number of internal queues.
Definition: queue-disc.cc:596
An "unforced" (random) drop.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
double m_vA
1.0 / (m_maxTh - m_minTh)
uint32_t m_countBytes
Number of bytes since last drop.
Ptr< const AttributeChecker > MakeBooleanChecker(void)
Definition: boolean.cc:121
double m_lInterm
The max probability of dropping a packet.
double GetValue(double min, double max)
Get the next random value, as a double in the specified range .
uint64_t GetBitRate() const
Get the underlying bitrate.
Definition: data-rate.cc:249
static constexpr const char * UNFORCED_MARK
Early probability marks.
uint32_t DropEarly(Ptr< QueueDiscItem > item, uint32_t qSize)
Check if a packet needs to be dropped due to probability mark.
RedQueueDisc()
RedQueueDisc Constructor.
double m_bottom
Lower bound for m_curMaxP in ARED.
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:1070
static Time Now(void)
Return the current simulation virtual time.
Definition: simulator.cc:249
virtual Ptr< QueueDiscItem > DoDequeue(void)
This function actually extracts a packet from the queue disc.
NS_LOG_LOGIC("Net device "<< nd<< " is not bridged")
void UpdateMaxP(double newAve)
Update m_curMaxP.
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
QueueDiscSizePolicy
Enumeration of the available policies to handle the queue disc size.
Definition: queue-disc.h:104
uint32_t m_old
0 when average queue first exceeds threshold
When m_maxTh < m_qAvg < m_minTh.
Used by queue discs with single internal queue.
Definition: queue-disc.h:106
void SetFengAdaptiveA(double a)
Set the alpha value to adapt m_curMaxP in Feng&#39;s Adaptive RED.
#define NS_LOG_WARN(msg)
Use NS_LOG to output a message of level LOG_WARN.
Definition: log.h:262
AttributeValue implementation for DataRate.
Definition: data-rate.h:242
DataRate m_linkBandwidth
Link bandwidth.
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:270
Time Seconds(double value)
Construct a Time in the indicated unit.
Definition: nstime.h:1007
Time m_interval
Time interval to update m_curMaxP.
bool SetMaxSize(QueueSize size)
Set the maximum size of the queue disc.
Definition: queue-disc.cc:483
bool m_isWait
True for waiting between dropped packets.
Time m_targetDelay
Target average queuing delay in ARED.
double GetAredBeta(void)
Get the beta value to adapt m_curMaxP.
double m_ptc
packet time constant in packets/second
virtual ~RedQueueDisc()
Destructor.
#define NS_LOG_ERROR(msg)
Use NS_LOG to output a message of level LOG_ERROR.
Definition: log.h:254
double m_top
Upper bound for m_curMaxP in ARED.
double Estimator(uint32_t nQueued, uint32_t m, double qAvg, double qW)
Compute the average queue size.
uint32_t m_meanPktSize
Avg pkt size.
void UpdateMaxPFeng(double newAve)
Update m_curMaxP based on Feng&#39;s Adaptive RED.
bool m_isFengAdaptive
True to enable Feng&#39;s Adaptive RED.
double CalculatePNew(void)
Returns a probability using these function parameters for the DropEarly function. ...
void SetAredAlpha(double alpha)
Set the alpha value to adapt m_curMaxP.
When m_qAvg > m_maxTh.
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
virtual void DoDispose(void)
Dispose of the object.
double ModifyP(double p, uint32_t size)
Returns a probability using these function parameters for the DropEarly function. ...
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
a unique identifier for an interface.
Definition: type-id.h:58
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:915
double m_vProb
Prob.
double m_maxTh
Maximum threshold for m_qAvg (bytes or packets), should be >= 2 * m_minTh.
QueueSize GetMaxSize(void) const
Get the maximum size of the queue disc.
Definition: queue-disc.cc:455
double m_a
Decrement parameter for m_curMaxP in Feng&#39;s Adaptive RED.
uint32_t GetNPackets(void) const
Get the number of packets stored by the queue disc.
Definition: queue-disc.cc:441
When m_qAvg < m_minTh.
bool m_isNs1Compat
Ns-1 compatibility.