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 
68 namespace ns3 {
69 
70 NS_LOG_COMPONENT_DEFINE ("RedQueueDisc");
71 
72 NS_OBJECT_ENSURE_REGISTERED (RedQueueDisc);
73 
75 {
76  static TypeId tid = TypeId ("ns3::RedQueueDisc")
77  .SetParent<QueueDisc> ()
78  .SetGroupName("TrafficControl")
79  .AddConstructor<RedQueueDisc> ()
80  .AddAttribute ("MeanPktSize",
81  "Average of packet size",
82  UintegerValue (500),
84  MakeUintegerChecker<uint32_t> ())
85  .AddAttribute ("IdlePktSize",
86  "Average packet size used during idle times. Used when m_cautions = 3",
87  UintegerValue (0),
89  MakeUintegerChecker<uint32_t> ())
90  .AddAttribute ("Wait",
91  "True for waiting between dropped packets",
92  BooleanValue (true),
95  .AddAttribute ("Gentle",
96  "True to increases dropping probability slowly when average queue exceeds maxthresh",
97  BooleanValue (true),
100  .AddAttribute ("ARED",
101  "True to enable ARED",
102  BooleanValue (false),
105  .AddAttribute ("AdaptMaxP",
106  "True to adapt m_curMaxP",
107  BooleanValue (false),
110  .AddAttribute ("FengAdaptive",
111  "True to enable Feng's Adaptive RED",
112  BooleanValue (false),
115  .AddAttribute ("NLRED",
116  "True to enable Nonlinear RED",
117  BooleanValue (false),
120  .AddAttribute ("MinTh",
121  "Minimum average length threshold in packets/bytes",
122  DoubleValue (5),
124  MakeDoubleChecker<double> ())
125  .AddAttribute ("MaxTh",
126  "Maximum average length threshold in packets/bytes",
127  DoubleValue (15),
129  MakeDoubleChecker<double> ())
130  .AddAttribute ("MaxSize",
131  "The maximum number of packets accepted by this queue disc",
132  QueueSizeValue (QueueSize ("25p")),
136  .AddAttribute ("QW",
137  "Queue weight related to the exponential weighted moving average (EWMA)",
138  DoubleValue (0.002),
140  MakeDoubleChecker <double> ())
141  .AddAttribute ("LInterm",
142  "The maximum probability of dropping a packet",
143  DoubleValue (50),
145  MakeDoubleChecker <double> ())
146  .AddAttribute ("TargetDelay",
147  "Target average queuing delay in ARED",
148  TimeValue (Seconds (0.005)),
150  MakeTimeChecker ())
151  .AddAttribute ("Interval",
152  "Time interval to update m_curMaxP",
153  TimeValue (Seconds (0.5)),
155  MakeTimeChecker ())
156  .AddAttribute ("Top",
157  "Upper bound for m_curMaxP in ARED",
158  DoubleValue (0.5),
160  MakeDoubleChecker <double> (0, 1))
161  .AddAttribute ("Bottom",
162  "Lower bound for m_curMaxP in ARED",
163  DoubleValue (0.0),
165  MakeDoubleChecker <double> (0, 1))
166  .AddAttribute ("Alpha",
167  "Increment parameter for m_curMaxP in ARED",
168  DoubleValue (0.01),
170  MakeDoubleChecker <double> (0, 1))
171  .AddAttribute ("Beta",
172  "Decrement parameter for m_curMaxP in ARED",
173  DoubleValue (0.9),
175  MakeDoubleChecker <double> (0, 1))
176  .AddAttribute ("FengAlpha",
177  "Decrement parameter for m_curMaxP in Feng's Adaptive RED",
178  DoubleValue (3.0),
180  MakeDoubleChecker <double> ())
181  .AddAttribute ("FengBeta",
182  "Increment parameter for m_curMaxP in Feng's Adaptive RED",
183  DoubleValue (2.0),
185  MakeDoubleChecker <double> ())
186  .AddAttribute ("LastSet",
187  "Store the last time m_curMaxP was updated",
188  TimeValue (Seconds (0.0)),
190  MakeTimeChecker ())
191  .AddAttribute ("Rtt",
192  "Round Trip Time to be considered while automatically setting m_bottom",
193  TimeValue (Seconds (0.1)),
195  MakeTimeChecker ())
196  .AddAttribute ("Ns1Compat",
197  "NS-1 compatibility",
198  BooleanValue (false),
201  .AddAttribute ("LinkBandwidth",
202  "The RED link bandwidth",
203  DataRateValue (DataRate ("1.5Mbps")),
206  .AddAttribute ("LinkDelay",
207  "The RED link delay",
208  TimeValue (MilliSeconds (20)),
210  MakeTimeChecker ())
211  .AddAttribute ("UseEcn",
212  "True to use ECN (packets are marked instead of being dropped)",
213  BooleanValue (false),
216  .AddAttribute ("UseHardDrop",
217  "True to always drop packets above max threshold",
218  BooleanValue (true),
221  ;
222 
223  return tid;
224 }
225 
228 {
229  NS_LOG_FUNCTION (this);
230  m_uv = CreateObject<UniformRandomVariable> ();
231 }
232 
234 {
235  NS_LOG_FUNCTION (this);
236 }
237 
238 void
240 {
241  NS_LOG_FUNCTION (this);
242  m_uv = 0;
244 }
245 
246 void
248 {
249  NS_LOG_FUNCTION (this << alpha);
250  m_alpha = alpha;
251 
252  if (m_alpha > 0.01)
253  {
254  NS_LOG_WARN ("Alpha value is above the recommended bound!");
255  }
256 }
257 
258 double
260 {
261  NS_LOG_FUNCTION (this);
262  return m_alpha;
263 }
264 
265 void
267 {
268  NS_LOG_FUNCTION (this << beta);
269  m_beta = beta;
270 
271  if (m_beta < 0.83)
272  {
273  NS_LOG_WARN ("Beta value is below the recommended bound!");
274  }
275 }
276 
277 double
279 {
280  NS_LOG_FUNCTION (this);
281  return m_beta;
282 }
283 
284 void
286 {
287  NS_LOG_FUNCTION (this << a);
288  m_a = a;
289 
290  if (m_a != 3)
291  {
292  NS_LOG_WARN ("Alpha value does not follow the recommendations!");
293  }
294 }
295 
296 double
298 {
299  NS_LOG_FUNCTION (this);
300  return m_a;
301 }
302 
303 void
305 {
306  NS_LOG_FUNCTION (this << b);
307  m_b = b;
308 
309  if (m_b != 2)
310  {
311  NS_LOG_WARN ("Beta value does not follow the recommendations!");
312  }
313 }
314 
315 double
317 {
318  NS_LOG_FUNCTION (this);
319  return m_b;
320 }
321 
322 void
323 RedQueueDisc::SetTh (double minTh, double maxTh)
324 {
325  NS_LOG_FUNCTION (this << minTh << maxTh);
326  NS_ASSERT (minTh <= maxTh);
327  m_minTh = minTh;
328  m_maxTh = maxTh;
329 }
330 
331 int64_t
333 {
334  NS_LOG_FUNCTION (this << stream);
335  m_uv->SetStream (stream);
336  return 1;
337 }
338 
339 bool
341 {
342  NS_LOG_FUNCTION (this << item);
343 
344  uint32_t nQueued = GetInternalQueue (0)->GetCurrentSize ().GetValue ();
345 
346  // simulate number of packets arrival during idle period
347  uint32_t m = 0;
348 
349  if (m_idle == 1)
350  {
351  NS_LOG_DEBUG ("RED Queue Disc is idle.");
352  Time now = Simulator::Now ();
353 
354  if (m_cautious == 3)
355  {
356  double ptc = m_ptc * m_meanPktSize / m_idlePktSize;
357  m = uint32_t (ptc * (now - m_idleTime).GetSeconds ());
358  }
359  else
360  {
361  m = uint32_t (m_ptc * (now - m_idleTime).GetSeconds ());
362  }
363 
364  m_idle = 0;
365  }
366 
367  m_qAvg = Estimator (nQueued, m + 1, m_qAvg, m_qW);
368 
369  NS_LOG_DEBUG ("\t bytesInQueue " << GetInternalQueue (0)->GetNBytes () << "\tQavg " << m_qAvg);
370  NS_LOG_DEBUG ("\t packetsInQueue " << GetInternalQueue (0)->GetNPackets () << "\tQavg " << m_qAvg);
371 
372  m_count++;
373  m_countBytes += item->GetSize ();
374 
375  uint32_t dropType = DTYPE_NONE;
376  if (m_qAvg >= m_minTh && nQueued > 1)
377  {
378  if ((!m_isGentle && m_qAvg >= m_maxTh) ||
379  (m_isGentle && m_qAvg >= 2 * m_maxTh))
380  {
381  NS_LOG_DEBUG ("adding DROP FORCED MARK");
382  dropType = DTYPE_FORCED;
383  }
384  else if (m_old == 0)
385  {
386  /*
387  * The average queue size has just crossed the
388  * threshold from below to above m_minTh, or
389  * from above m_minTh with an empty queue to
390  * above m_minTh with a nonempty queue.
391  */
392  m_count = 1;
393  m_countBytes = item->GetSize ();
394  m_old = 1;
395  }
396  else if (DropEarly (item, nQueued))
397  {
398  NS_LOG_LOGIC ("DropEarly returns 1");
399  dropType = DTYPE_UNFORCED;
400  }
401  }
402  else
403  {
404  // No packets are being dropped
405  m_vProb = 0.0;
406  m_old = 0;
407  }
408 
409  if (dropType == DTYPE_UNFORCED)
410  {
411  if (!m_useEcn || !Mark (item, UNFORCED_MARK))
412  {
413  NS_LOG_DEBUG ("\t Dropping due to Prob Mark " << m_qAvg);
415  return false;
416  }
417  NS_LOG_DEBUG ("\t Marking due to Prob Mark " << m_qAvg);
418  }
419  else if (dropType == DTYPE_FORCED)
420  {
421  if (m_useHardDrop || !m_useEcn || !Mark (item, FORCED_MARK))
422  {
423  NS_LOG_DEBUG ("\t Dropping due to Hard Mark " << m_qAvg);
425  if (m_isNs1Compat)
426  {
427  m_count = 0;
428  m_countBytes = 0;
429  }
430  return false;
431  }
432  NS_LOG_DEBUG ("\t Marking due to Hard Mark " << m_qAvg);
433  }
434 
435  bool retval = GetInternalQueue (0)->Enqueue (item);
436 
437  // If Queue::Enqueue fails, QueueDisc::DropBeforeEnqueue is called by the
438  // internal queue because QueueDisc::AddInternalQueue sets the trace callback
439 
440  NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
441  NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
442 
443  return retval;
444 }
445 
446 /*
447  * Note: if the link bandwidth changes in the course of the
448  * simulation, the bandwidth-dependent RED parameters do not change.
449  * This should be fixed, but it would require some extra parameters,
450  * and didn't seem worth the trouble...
451  */
452 void
454 {
455  NS_LOG_FUNCTION (this);
456  NS_LOG_INFO ("Initializing RED params.");
457 
458  m_cautious = 0;
460 
461  if (m_isARED)
462  {
463  // Set m_minTh, m_maxTh and m_qW to zero for automatic setting
464  m_minTh = 0;
465  m_maxTh = 0;
466  m_qW = 0;
467 
468  // Turn on m_isAdaptMaxP to adapt m_curMaxP
469  m_isAdaptMaxP = true;
470  }
471 
472  if (m_isFengAdaptive)
473  {
474  // Initialize m_fengStatus
476  }
477 
478  if (m_minTh == 0 && m_maxTh == 0)
479  {
480  m_minTh = 5.0;
481 
482  // set m_minTh to max(m_minTh, targetqueue/2.0) [Ref: http://www.icir.org/floyd/papers/adaptiveRed.pdf]
483  double targetqueue = m_targetDelay.GetSeconds() * m_ptc;
484 
485  if (m_minTh < targetqueue / 2.0 )
486  {
487  m_minTh = targetqueue / 2.0;
488  }
490  {
492  }
493 
494  // set m_maxTh to three times m_minTh [Ref: http://www.icir.org/floyd/papers/adaptiveRed.pdf]
495  m_maxTh = 3 * m_minTh;
496  }
497 
499 
500  m_qAvg = 0.0;
501  m_count = 0;
502  m_countBytes = 0;
503  m_old = 0;
504  m_idle = 1;
505 
506  double th_diff = (m_maxTh - m_minTh);
507  if (th_diff == 0)
508  {
509  th_diff = 1.0;
510  }
511  m_vA = 1.0 / th_diff;
512  m_curMaxP = 1.0 / m_lInterm;
513  m_vB = -m_minTh / th_diff;
514 
515  if (m_isGentle)
516  {
517  m_vC = (1.0 - m_curMaxP) / m_maxTh;
518  m_vD = 2.0 * m_curMaxP - 1.0;
519  }
520  m_idleTime = NanoSeconds (0);
521 
522 /*
523  * If m_qW=0, set it to a reasonable value of 1-exp(-1/C)
524  * This corresponds to choosing m_qW to be of that value for
525  * which the packet time constant -1/ln(1-m)qW) per default RTT
526  * of 100ms is an order of magnitude more than the link capacity, C.
527  *
528  * If m_qW=-1, then the queue weight is set to be a function of
529  * the bandwidth and the link propagation delay. In particular,
530  * the default RTT is assumed to be three times the link delay and
531  * transmission delay, if this gives a default RTT greater than 100 ms.
532  *
533  * If m_qW=-2, set it to a reasonable value of 1-exp(-10/C).
534  */
535  if (m_qW == 0.0)
536  {
537  m_qW = 1.0 - std::exp (-1.0 / m_ptc);
538  }
539  else if (m_qW == -1.0)
540  {
541  double rtt = 3.0 * (m_linkDelay.GetSeconds () + 1.0 / m_ptc);
542 
543  if (rtt < 0.1)
544  {
545  rtt = 0.1;
546  }
547  m_qW = 1.0 - std::exp (-1.0 / (10 * rtt * m_ptc));
548  }
549  else if (m_qW == -2.0)
550  {
551  m_qW = 1.0 - std::exp (-10.0 / m_ptc);
552  }
553 
554  if (m_bottom == 0)
555  {
556  m_bottom = 0.01;
557  // Set bottom to at most 1/W, where W is the delay-bandwidth
558  // product in packets for a connection.
559  // So W = m_linkBandwidth.GetBitRate () / (8.0 * m_meanPktSize * m_rtt.GetSeconds())
560  double bottom1 = (8.0 * m_meanPktSize * m_rtt.GetSeconds()) / m_linkBandwidth.GetBitRate();
561  if (bottom1 < m_bottom)
562  {
563  m_bottom = bottom1;
564  }
565  }
566 
567  NS_LOG_DEBUG ("\tm_delay " << m_linkDelay.GetSeconds () << "; m_isWait "
568  << m_isWait << "; m_qW " << m_qW << "; m_ptc " << m_ptc
569  << "; m_minTh " << m_minTh << "; m_maxTh " << m_maxTh
570  << "; m_isGentle " << m_isGentle << "; th_diff " << th_diff
571  << "; lInterm " << m_lInterm << "; va " << m_vA << "; cur_max_p "
572  << m_curMaxP << "; v_b " << m_vB << "; m_vC "
573  << m_vC << "; m_vD " << m_vD);
574 }
575 
576 // Updating m_curMaxP, following the pseudocode
577 // from: A Self-Configuring RED Gateway, INFOCOMM '99.
578 // They recommend m_a = 3, and m_b = 2.
579 void
581 {
582  NS_LOG_FUNCTION (this << newAve);
583 
584  if (m_minTh < newAve && newAve < m_maxTh)
585  {
587  }
588  else if (newAve < m_minTh && m_fengStatus != Below)
589  {
591  m_curMaxP = m_curMaxP / m_a;
592  }
593  else if (newAve > m_maxTh && m_fengStatus != Above)
594  {
596  m_curMaxP = m_curMaxP * m_b;
597  }
598 }
599 
600 // Update m_curMaxP to keep the average queue length within the target range.
601 void
603 {
604  NS_LOG_FUNCTION (this << newAve);
605 
606  Time now = Simulator::Now ();
607  double m_part = 0.4 * (m_maxTh - m_minTh);
608  // AIMD rule to keep target Q~1/2(m_minTh + m_maxTh)
609  if (newAve < m_minTh + m_part && m_curMaxP > m_bottom)
610  {
611  // we should increase the average queue size, so decrease m_curMaxP
613  m_lastSet = now;
614  }
615  else if (newAve > m_maxTh - m_part && m_top > m_curMaxP)
616  {
617  // we should decrease the average queue size, so increase m_curMaxP
618  double alpha = m_alpha;
619  if (alpha > 0.25 * m_curMaxP)
620  {
621  alpha = 0.25 * m_curMaxP;
622  }
624  m_lastSet = now;
625  }
626 }
627 
628 // Compute the average queue size
629 double
630 RedQueueDisc::Estimator (uint32_t nQueued, uint32_t m, double qAvg, double qW)
631 {
632  NS_LOG_FUNCTION (this << nQueued << m << qAvg << qW);
633 
634  double newAve = qAvg * std::pow (1.0 - qW, m);
635  newAve += qW * nQueued;
636 
637  Time now = Simulator::Now ();
638  if (m_isAdaptMaxP && now > m_lastSet + m_interval)
639  {
640  UpdateMaxP (newAve);
641  }
642  else if (m_isFengAdaptive)
643  {
644  UpdateMaxPFeng (newAve); // Update m_curMaxP in MIMD fashion.
645  }
646 
647  return newAve;
648 }
649 
650 // Check if packet p needs to be dropped due to probability mark
651 uint32_t
653 {
654  NS_LOG_FUNCTION (this << item << qSize);
655 
656  double prob1 = CalculatePNew ();
657  m_vProb = ModifyP (prob1, item->GetSize ());
658 
659  // Drop probability is computed, pick random number and act
660  if (m_cautious == 1)
661  {
662  /*
663  * Don't drop/mark if the instantaneous queue is much below the average.
664  * For experimental purposes only.
665  * pkts: the number of packets arriving in 50 ms
666  */
667  double pkts = m_ptc * 0.05;
668  double fraction = std::pow ((1 - m_qW), pkts);
669 
670  if ((double) qSize < fraction * m_qAvg)
671  {
672  // Queue could have been empty for 0.05 seconds
673  return 0;
674  }
675  }
676 
677  double u = m_uv->GetValue ();
678 
679  if (m_cautious == 2)
680  {
681  /*
682  * Decrease the drop probability if the instantaneous
683  * queue is much below the average.
684  * For experimental purposes only.
685  * pkts: the number of packets arriving in 50 ms
686  */
687  double pkts = m_ptc * 0.05;
688  double fraction = std::pow ((1 - m_qW), pkts);
689  double ratio = qSize / (fraction * m_qAvg);
690 
691  if (ratio < 1.0)
692  {
693  u *= 1.0 / ratio;
694  }
695  }
696 
697  if (u <= m_vProb)
698  {
699  NS_LOG_LOGIC ("u <= m_vProb; u " << u << "; m_vProb " << m_vProb);
700 
701  // DROP or MARK
702  m_count = 0;
703  m_countBytes = 0;
705 
706  return 1; // drop
707  }
708 
709  return 0; // no drop/mark
710 }
711 
712 // Returns a probability using these function parameters for the DropEarly function
713 double
715 {
716  NS_LOG_FUNCTION (this);
717  double p;
718 
719  if (m_isGentle && m_qAvg >= m_maxTh)
720  {
721  // p ranges from m_curMaxP to 1 as the average queue
722  // size ranges from m_maxTh to twice m_maxTh
723  p = m_vC * m_qAvg + m_vD;
724  }
725  else if (!m_isGentle && m_qAvg >= m_maxTh)
726  {
727  /*
728  * OLD: p continues to range linearly above m_curMaxP as
729  * the average queue size ranges above m_maxTh.
730  * NEW: p is set to 1.0
731  */
732  p = 1.0;
733  }
734  else
735  {
736  /*
737  * p ranges from 0 to m_curMaxP as the average queue size ranges from
738  * m_minTh to m_maxTh
739  */
740  p = m_vA * m_qAvg + m_vB;
741 
742  if (m_isNonlinear)
743  {
744  p *= p * 1.5;
745  }
746 
747  p *= m_curMaxP;
748  }
749 
750  if (p > 1.0)
751  {
752  p = 1.0;
753  }
754 
755  return p;
756 }
757 
758 // Returns a probability using these function parameters for the DropEarly function
759 double
760 RedQueueDisc::ModifyP (double p, uint32_t size)
761 {
762  NS_LOG_FUNCTION (this << p << size);
763  double count1 = (double) m_count;
764 
766  {
767  count1 = (double) (m_countBytes / m_meanPktSize);
768  }
769 
770  if (m_isWait)
771  {
772  if (count1 * p < 1.0)
773  {
774  p = 0.0;
775  }
776  else if (count1 * p < 2.0)
777  {
778  p /= (2.0 - count1 * p);
779  }
780  else
781  {
782  p = 1.0;
783  }
784  }
785  else
786  {
787  if (count1 * p < 1.0)
788  {
789  p /= (1.0 - count1 * p);
790  }
791  else
792  {
793  p = 1.0;
794  }
795  }
796 
797  if ((GetMaxSize ().GetUnit () == QueueSizeUnit::BYTES) && (p < 1.0))
798  {
799  p = (p * size) / m_meanPktSize;
800  }
801 
802  if (p > 1.0)
803  {
804  p = 1.0;
805  }
806 
807  return p;
808 }
809 
812 {
813  NS_LOG_FUNCTION (this);
814 
815  if (GetInternalQueue (0)->IsEmpty ())
816  {
817  NS_LOG_LOGIC ("Queue empty");
818  m_idle = 1;
820 
821  return 0;
822  }
823  else
824  {
825  m_idle = 0;
826  Ptr<QueueDiscItem> item = GetInternalQueue (0)->Dequeue ();
827 
828  NS_LOG_LOGIC ("Popped " << item);
829 
830  NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
831  NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
832 
833  return item;
834  }
835 }
836 
839 {
840  NS_LOG_FUNCTION (this);
841  if (GetInternalQueue (0)->IsEmpty ())
842  {
843  NS_LOG_LOGIC ("Queue empty");
844  return 0;
845  }
846 
847  Ptr<const QueueDiscItem> item = GetInternalQueue (0)->Peek ();
848 
849  NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
850  NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
851 
852  return item;
853 }
854 
855 bool
857 {
858  NS_LOG_FUNCTION (this);
859  if (GetNQueueDiscClasses () > 0)
860  {
861  NS_LOG_ERROR ("RedQueueDisc cannot have classes");
862  return false;
863  }
864 
865  if (GetNPacketFilters () > 0)
866  {
867  NS_LOG_ERROR ("RedQueueDisc cannot have packet filters");
868  return false;
869  }
870 
871  if (GetNInternalQueues () == 0)
872  {
873  // add a DropTail queue
875  ("MaxSize", QueueSizeValue (GetMaxSize ())));
876  }
877 
878  if (GetNInternalQueues () != 1)
879  {
880  NS_LOG_ERROR ("RedQueueDisc needs 1 internal queue");
881  return false;
882  }
883 
885  {
886  NS_LOG_ERROR ("m_isAdaptMaxP and m_isFengAdaptive cannot be simultaneously true");
887  }
888 
889  return true;
890 }
891 
892 } // namespace ns3
AttributeValue implementation for Boolean.
Definition: boolean.h:37
Class for representing data rates.
Definition: data-rate.h:89
uint64_t GetBitRate() const
Get the underlying bitrate.
Definition: data-rate.cc:287
AttributeValue implementation for DataRate.
Definition: data-rate.h:298
This class can be used to hold variables of floating point type such as 'double' or 'float'.
Definition: double.h:41
Introspection did not find any typical Config paths.
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:74
QueueDisc is an abstract base class providing the interface and implementing the operations common to...
Definition: queue-disc.h:181
void AddInternalQueue(Ptr< InternalQueue > queue)
Add an internal queue to the tail of the list of queues.
Definition: queue-disc.cc:579
uint32_t GetNBytes(void) const
Get the amount of bytes stored by the queue disc.
Definition: queue-disc.cc:445
QueueSize GetMaxSize(void) const
Get the maximum size of the queue disc.
Definition: queue-disc.cc:452
Ptr< InternalQueue > GetInternalQueue(std::size_t i) const
Get the i-th internal queue.
Definition: queue-disc.cc:599
std::size_t GetNPacketFilters(void) const
Get the number of packet filters.
Definition: queue-disc.cc:626
uint32_t GetNPackets(void) const
Get the number of packets stored by the queue disc.
Definition: queue-disc.cc:438
std::size_t GetNQueueDiscClasses(void) const
Get the number of queue disc classes.
Definition: queue-disc.cc:667
bool SetMaxSize(QueueSize size)
Set the maximum size of the queue disc.
Definition: queue-disc.cc:480
virtual void DoDispose(void)
Dispose of the object.
Definition: queue-disc.cc:382
std::size_t GetNInternalQueues(void) const
Get the number of internal queues.
Definition: queue-disc.cc:606
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:816
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:727
Class for representing queue sizes.
Definition: queue-size.h:95
QueueSizeUnit GetUnit() const
Get the underlying unit.
Definition: queue-size.cc:168
AttributeValue implementation for QueueSize.
Definition: queue-size.h:221
void SetStream(int64_t stream)
Specifies the stream number for the RngStream.
A RED packet queue disc.
Time m_idleTime
Start of current idle period.
Time m_linkDelay
Link delay.
RedQueueDisc()
RedQueueDisc Constructor.
void UpdateMaxPFeng(double newAve)
Update m_curMaxP based on Feng's Adaptive RED.
DataRate m_linkBandwidth
Link bandwidth.
double m_vA
1.0 / (m_maxTh - m_minTh)
void SetFengAdaptiveB(double b)
Set the beta value to adapt m_curMaxP in Feng's Adaptive RED.
Time m_rtt
Rtt to be considered while automatically setting m_bottom in ARED.
static constexpr const char * FORCED_DROP
Forced drops, m_qAvg > m_maxTh.
@ Above
When m_qAvg > m_maxTh.
@ Between
When m_maxTh < m_qAvg < m_minTh.
@ Below
When m_qAvg < m_minTh.
static constexpr const char * UNFORCED_DROP
Early probability drops.
double ModifyP(double p, uint32_t size)
Returns a probability using these function parameters for the DropEarly function.
double m_a
Decrement parameter for m_curMaxP in Feng's Adaptive RED.
virtual Ptr< QueueDiscItem > DoDequeue(void)
This function actually extracts a packet from the queue disc.
void SetAredBeta(double beta)
Set the beta value to adapt m_curMaxP.
bool m_isAdaptMaxP
True to adapt m_curMaxP.
void SetTh(double minTh, double maxTh)
Set the thresh limits of RED.
uint32_t m_cautious
0 for default RED 1 experimental (see red-queue-disc.cc) 2 experimental (see red-queue-disc....
static TypeId GetTypeId(void)
Get the type ID.
double m_alpha
Increment parameter for m_curMaxP in ARED.
virtual ~RedQueueDisc()
Destructor.
bool m_isARED
True to enable Adaptive RED.
Time m_interval
Time interval to update m_curMaxP.
int64_t AssignStreams(int64_t stream)
Assign a fixed random variable stream number to the random variables used by this model.
double GetFengAdaptiveB(void)
Get the beta value to adapt m_curMaxP in Feng's Adaptive RED.
FengStatus m_fengStatus
For use in Feng's Adaptive RED.
bool m_useHardDrop
True if packets are always dropped above max threshold.
static constexpr const char * UNFORCED_MARK
Early probability marks.
uint32_t m_old
0 when average queue first exceeds threshold
void SetFengAdaptiveA(double a)
Set the alpha value to adapt m_curMaxP in Feng's Adaptive RED.
bool m_isWait
True for waiting between dropped packets.
bool m_useEcn
True if ECN is used (packets are marked instead of being dropped)
@ DTYPE_UNFORCED
An "unforced" (random) drop.
@ DTYPE_FORCED
A "forced" drop.
@ DTYPE_NONE
Ok, no drop.
double m_maxTh
Maximum threshold for m_qAvg (bytes or packets), should be >= 2 * m_minTh.
virtual Ptr< const QueueDiscItem > DoPeek(void)
Return a copy of the next packet the queue disc will extract.
static constexpr const char * FORCED_MARK
Forced marks, m_qAvg > m_maxTh.
bool m_isNonlinear
True to enable Nonlinear RED.
double m_minTh
Minimum threshold for m_qAvg (bytes or packets)
double m_top
Upper bound for m_curMaxP in ARED.
uint32_t m_meanPktSize
Avg pkt size.
double m_beta
Decrement parameter for m_curMaxP in ARED.
double m_lInterm
The max probability of dropping a packet.
uint32_t m_countBytes
Number of bytes since last drop.
virtual bool CheckConfig(void)
Check whether the current configuration is correct.
uint32_t DropEarly(Ptr< QueueDiscItem > item, uint32_t qSize)
Check if a packet needs to be dropped due to probability mark.
void SetAredAlpha(double alpha)
Set the alpha value to adapt m_curMaxP.
double CalculatePNew(void)
Returns a probability using these function parameters for the DropEarly function.
bool m_isNs1Compat
Ns-1 compatibility.
double Estimator(uint32_t nQueued, uint32_t m, double qAvg, double qW)
Compute the average queue size.
double m_vB
-m_minTh / (m_maxTh - m_minTh)
double m_b
Increment parameter for m_curMaxP in Feng's Adaptive RED.
double m_bottom
Lower bound for m_curMaxP in ARED.
Time m_lastSet
Last time m_curMaxP was updated.
Time m_targetDelay
Target average queuing delay in ARED.
double m_ptc
packet time constant in packets/second
double m_vProb
Prob.
double GetFengAdaptiveA(void)
Get the alpha value to adapt m_curMaxP in Feng's Adaptive RED.
void UpdateMaxP(double newAve)
Update m_curMaxP.
bool m_isFengAdaptive
True to enable Feng's Adaptive RED.
virtual void DoDispose(void)
Dispose of the object.
uint32_t m_count
Number of packets since last random number generation.
uint32_t m_idle
0/1 idle status
Ptr< UniformRandomVariable > m_uv
rng stream
double GetAredBeta(void)
Get the beta value to adapt m_curMaxP.
double m_vD
2.0 * m_curMaxP - 1.0 - used in "gentle" mode
double m_qAvg
Average queue length.
bool m_isGentle
True to increase dropping prob.
virtual void InitializeParams(void)
Initialize the queue parameters.
double GetAredAlpha(void)
Get the alpha value to adapt m_curMaxP.
double m_vC
(1.0 - m_curMaxP) / m_maxTh - used in "gentle" mode
uint32_t m_idlePktSize
Avg pkt size used during idle times.
virtual bool DoEnqueue(Ptr< QueueDiscItem > item)
This function actually enqueues a packet into the queue disc.
double m_qW
Queue weight given to cur queue size sample.
double m_curMaxP
Current max_p.
static Time Now(void)
Return the current simulation virtual time.
Definition: simulator.cc:195
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:103
double GetSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:379
AttributeValue implementation for Time.
Definition: nstime.h:1308
a unique identifier for an interface.
Definition: type-id.h:59
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:922
Hold an unsigned integer type.
Definition: uinteger.h:44
double GetValue(double min, double max)
Get the next random value, as a double in the specified range .
#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
Ptr< const AttributeChecker > MakeBooleanChecker(void)
Definition: boolean.cc:121
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:85
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:298
Ptr< const AttributeChecker > MakeDataRateChecker(void)
Definition: data-rate.cc:30
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
Ptr< const AttributeChecker > MakeQueueSizeChecker(void)
Definition: queue-size.cc:28
Ptr< const AttributeAccessor > MakeQueueSizeAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method.
Definition: queue-size.h:221
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:1309
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
#define NS_LOG_ERROR(msg)
Use NS_LOG to output a message of level LOG_ERROR.
Definition: log.h:257
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:273
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:289
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
#define NS_LOG_WARN(msg)
Use NS_LOG to output a message of level LOG_WARN.
Definition: log.h:265
#define NS_LOG_INFO(msg)
Use NS_LOG to output a message of level LOG_INFO.
Definition: log.h:281
Ptr< T > CreateObjectWithAttributes(Args... args)
Allocate an Object on the heap and initialize with a set of attributes.
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
@ BYTES
Use number of bytes for queue size.
Definition: queue-size.h:45
Time NanoSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition: nstime.h:1268
Time Seconds(double value)
Construct a Time in the indicated unit.
Definition: nstime.h:1244
Time MilliSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition: nstime.h:1252
QueueDiscSizePolicy
Enumeration of the available policies to handle the queue disc size.
Definition: queue-disc.h:104
@ SINGLE_INTERNAL_QUEUE
Used by queue discs with single internal queue.
Definition: queue-disc.h:105
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Ptr< const AttributeChecker > MakeTimeChecker(const Time min, const Time max)
Helper to make a Time checker with bounded range.
Definition: time.cc:522
float alpha
Plot alpha value (transparency)