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 ("Mode",
82  "Determines unit for QueueLimit",
85  MakeEnumChecker (QUEUE_DISC_MODE_BYTES, "QUEUE_DISC_MODE_BYTES",
86  QUEUE_DISC_MODE_PACKETS, "QUEUE_DISC_MODE_PACKETS"))
87  .AddAttribute ("MeanPktSize",
88  "Average of packet size",
89  UintegerValue (500),
91  MakeUintegerChecker<uint32_t> ())
92  .AddAttribute ("IdlePktSize",
93  "Average packet size used during idle times. Used when m_cautions = 3",
94  UintegerValue (0),
96  MakeUintegerChecker<uint32_t> ())
97  .AddAttribute ("Wait",
98  "True for waiting between dropped packets",
99  BooleanValue (true),
102  .AddAttribute ("Gentle",
103  "True to increases dropping probability slowly when average queue exceeds maxthresh",
104  BooleanValue (true),
107  .AddAttribute ("ARED",
108  "True to enable ARED",
109  BooleanValue (false),
112  .AddAttribute ("AdaptMaxP",
113  "True to adapt m_curMaxP",
114  BooleanValue (false),
117  .AddAttribute ("FengAdaptive",
118  "True to enable Feng's Adaptive RED",
119  BooleanValue (false),
122  .AddAttribute ("NLRED",
123  "True to enable Nonlinear RED",
124  BooleanValue (false),
127  .AddAttribute ("MinTh",
128  "Minimum average length threshold in packets/bytes",
129  DoubleValue (5),
131  MakeDoubleChecker<double> ())
132  .AddAttribute ("MaxTh",
133  "Maximum average length threshold in packets/bytes",
134  DoubleValue (15),
136  MakeDoubleChecker<double> ())
137  .AddAttribute ("QueueLimit",
138  "Queue limit in bytes/packets",
139  UintegerValue (25),
141  MakeUintegerChecker<uint32_t> ())
142  .AddAttribute ("QW",
143  "Queue weight related to the exponential weighted moving average (EWMA)",
144  DoubleValue (0.002),
146  MakeDoubleChecker <double> ())
147  .AddAttribute ("LInterm",
148  "The maximum probability of dropping a packet",
149  DoubleValue (50),
151  MakeDoubleChecker <double> ())
152  .AddAttribute ("TargetDelay",
153  "Target average queuing delay in ARED",
154  TimeValue (Seconds (0.005)),
156  MakeTimeChecker ())
157  .AddAttribute ("Interval",
158  "Time interval to update m_curMaxP",
159  TimeValue (Seconds (0.5)),
161  MakeTimeChecker ())
162  .AddAttribute ("Top",
163  "Upper bound for m_curMaxP in ARED",
164  DoubleValue (0.5),
166  MakeDoubleChecker <double> (0, 1))
167  .AddAttribute ("Bottom",
168  "Lower bound for m_curMaxP in ARED",
169  DoubleValue (0.0),
171  MakeDoubleChecker <double> (0, 1))
172  .AddAttribute ("Alpha",
173  "Increment parameter for m_curMaxP in ARED",
174  DoubleValue (0.01),
176  MakeDoubleChecker <double> (0, 1))
177  .AddAttribute ("Beta",
178  "Decrement parameter for m_curMaxP in ARED",
179  DoubleValue (0.9),
181  MakeDoubleChecker <double> (0, 1))
182  .AddAttribute ("FengAlpha",
183  "Decrement parameter for m_curMaxP in Feng's Adaptive RED",
184  DoubleValue (3.0),
186  MakeDoubleChecker <double> ())
187  .AddAttribute ("FengBeta",
188  "Increment parameter for m_curMaxP in Feng's Adaptive RED",
189  DoubleValue (2.0),
191  MakeDoubleChecker <double> ())
192  .AddAttribute ("LastSet",
193  "Store the last time m_curMaxP was updated",
194  TimeValue (Seconds (0.0)),
196  MakeTimeChecker ())
197  .AddAttribute ("Rtt",
198  "Round Trip Time to be considered while automatically setting m_bottom",
199  TimeValue (Seconds (0.1)),
201  MakeTimeChecker ())
202  .AddAttribute ("Ns1Compat",
203  "NS-1 compatibility",
204  BooleanValue (false),
207  .AddAttribute ("LinkBandwidth",
208  "The RED link bandwidth",
209  DataRateValue (DataRate ("1.5Mbps")),
212  .AddAttribute ("LinkDelay",
213  "The RED link delay",
214  TimeValue (MilliSeconds (20)),
216  MakeTimeChecker ())
217  .AddAttribute ("UseEcn",
218  "True to use ECN (packets are marked instead of being dropped)",
219  BooleanValue (false),
222  .AddAttribute ("UseHardDrop",
223  "True to always drop packets above max threshold",
224  BooleanValue (true),
227  ;
228 
229  return tid;
230 }
231 
233  QueueDisc ()
234 {
235  NS_LOG_FUNCTION (this);
236  m_uv = CreateObject<UniformRandomVariable> ();
237 }
238 
240 {
241  NS_LOG_FUNCTION (this);
242 }
243 
244 void
246 {
247  NS_LOG_FUNCTION (this);
248  m_uv = 0;
250 }
251 
252 void
254 {
255  NS_LOG_FUNCTION (this << mode);
256  m_mode = mode;
257 }
258 
261 {
262  NS_LOG_FUNCTION (this);
263  return m_mode;
264 }
265 
266 void
268 {
269  NS_LOG_FUNCTION (this << alpha);
270  m_alpha = alpha;
271 
272  if (m_alpha > 0.01)
273  {
274  NS_LOG_WARN ("Alpha value is above the recommended bound!");
275  }
276 }
277 
278 double
280 {
281  NS_LOG_FUNCTION (this);
282  return m_alpha;
283 }
284 
285 void
287 {
288  NS_LOG_FUNCTION (this << beta);
289  m_beta = beta;
290 
291  if (m_beta < 0.83)
292  {
293  NS_LOG_WARN ("Beta value is below the recommended bound!");
294  }
295 }
296 
297 double
299 {
300  NS_LOG_FUNCTION (this);
301  return m_beta;
302 }
303 
304 void
306 {
307  NS_LOG_FUNCTION (this << a);
308  m_a = a;
309 
310  if (m_a != 3)
311  {
312  NS_LOG_WARN ("Alpha value does not follow the recommendations!");
313  }
314 }
315 
316 double
318 {
319  NS_LOG_FUNCTION (this);
320  return m_a;
321 }
322 
323 void
325 {
326  NS_LOG_FUNCTION (this << b);
327  m_b = b;
328 
329  if (m_b != 2)
330  {
331  NS_LOG_WARN ("Beta value does not follow the recommendations!");
332  }
333 }
334 
335 double
337 {
338  NS_LOG_FUNCTION (this);
339  return m_b;
340 }
341 
342 void
344 {
345  NS_LOG_FUNCTION (this << lim);
346  m_queueLimit = lim;
347 }
348 
349 void
350 RedQueueDisc::SetTh (double minTh, double maxTh)
351 {
352  NS_LOG_FUNCTION (this << minTh << maxTh);
353  NS_ASSERT (minTh <= maxTh);
354  m_minTh = minTh;
355  m_maxTh = maxTh;
356 }
357 
358 int64_t
360 {
361  NS_LOG_FUNCTION (this << stream);
362  m_uv->SetStream (stream);
363  return 1;
364 }
365 
366 bool
368 {
369  NS_LOG_FUNCTION (this << item);
370 
371  uint32_t nQueued = 0;
372 
373  if (GetMode () == QUEUE_DISC_MODE_BYTES)
374  {
375  NS_LOG_DEBUG ("Enqueue in bytes mode");
376  nQueued = GetInternalQueue (0)->GetNBytes ();
377  }
378  else if (GetMode () == QUEUE_DISC_MODE_PACKETS)
379  {
380  NS_LOG_DEBUG ("Enqueue in packets mode");
381  nQueued = GetInternalQueue (0)->GetNPackets ();
382  }
383 
384  // simulate number of packets arrival during idle period
385  uint32_t m = 0;
386 
387  if (m_idle == 1)
388  {
389  NS_LOG_DEBUG ("RED Queue Disc is idle.");
390  Time now = Simulator::Now ();
391 
392  if (m_cautious == 3)
393  {
394  double ptc = m_ptc * m_meanPktSize / m_idlePktSize;
395  m = uint32_t (ptc * (now - m_idleTime).GetSeconds ());
396  }
397  else
398  {
399  m = uint32_t (m_ptc * (now - m_idleTime).GetSeconds ());
400  }
401 
402  m_idle = 0;
403  }
404 
405  m_qAvg = Estimator (nQueued, m + 1, m_qAvg, m_qW);
406 
407  NS_LOG_DEBUG ("\t bytesInQueue " << GetInternalQueue (0)->GetNBytes () << "\tQavg " << m_qAvg);
408  NS_LOG_DEBUG ("\t packetsInQueue " << GetInternalQueue (0)->GetNPackets () << "\tQavg " << m_qAvg);
409 
410  m_count++;
411  m_countBytes += item->GetSize ();
412 
413  uint32_t dropType = DTYPE_NONE;
414  if (m_qAvg >= m_minTh && nQueued > 1)
415  {
416  if ((!m_isGentle && m_qAvg >= m_maxTh) ||
417  (m_isGentle && m_qAvg >= 2 * m_maxTh))
418  {
419  NS_LOG_DEBUG ("adding DROP FORCED MARK");
420  dropType = DTYPE_FORCED;
421  }
422  else if (m_old == 0)
423  {
424  /*
425  * The average queue size has just crossed the
426  * threshold from below to above m_minTh, or
427  * from above m_minTh with an empty queue to
428  * above m_minTh with a nonempty queue.
429  */
430  m_count = 1;
431  m_countBytes = item->GetSize ();
432  m_old = 1;
433  }
434  else if (DropEarly (item, nQueued))
435  {
436  NS_LOG_LOGIC ("DropEarly returns 1");
437  dropType = DTYPE_UNFORCED;
438  }
439  }
440  else
441  {
442  // No packets are being dropped
443  m_vProb = 0.0;
444  m_old = 0;
445  }
446 
447  if (dropType == DTYPE_UNFORCED)
448  {
449  if (!m_useEcn || !Mark (item, UNFORCED_MARK))
450  {
451  NS_LOG_DEBUG ("\t Dropping due to Prob Mark " << m_qAvg);
453  return false;
454  }
455  NS_LOG_DEBUG ("\t Marking due to Prob Mark " << m_qAvg);
456  }
457  else if (dropType == DTYPE_FORCED)
458  {
459  if (m_useHardDrop || !m_useEcn || !Mark (item, FORCED_MARK))
460  {
461  NS_LOG_DEBUG ("\t Dropping due to Hard Mark " << m_qAvg);
463  if (m_isNs1Compat)
464  {
465  m_count = 0;
466  m_countBytes = 0;
467  }
468  return false;
469  }
470  NS_LOG_DEBUG ("\t Marking due to Hard Mark " << m_qAvg);
471  }
472 
473  bool retval = GetInternalQueue (0)->Enqueue (item);
474 
475  // If Queue::Enqueue fails, QueueDisc::DropBeforeEnqueue is called by the
476  // internal queue because QueueDisc::AddInternalQueue sets the trace callback
477 
478  NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
479  NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
480 
481  return retval;
482 }
483 
484 /*
485  * Note: if the link bandwidth changes in the course of the
486  * simulation, the bandwidth-dependent RED parameters do not change.
487  * This should be fixed, but it would require some extra parameters,
488  * and didn't seem worth the trouble...
489  */
490 void
492 {
493  NS_LOG_FUNCTION (this);
494  NS_LOG_INFO ("Initializing RED params.");
495 
496  m_cautious = 0;
498 
499  if (m_isARED)
500  {
501  // Set m_minTh, m_maxTh and m_qW to zero for automatic setting
502  m_minTh = 0;
503  m_maxTh = 0;
504  m_qW = 0;
505 
506  // Turn on m_isAdaptMaxP to adapt m_curMaxP
507  m_isAdaptMaxP = true;
508  }
509 
510  if (m_isFengAdaptive)
511  {
512  // Initialize m_fengStatus
514  }
515 
516  if (m_minTh == 0 && m_maxTh == 0)
517  {
518  m_minTh = 5.0;
519 
520  // set m_minTh to max(m_minTh, targetqueue/2.0) [Ref: http://www.icir.org/floyd/papers/adaptiveRed.pdf]
521  double targetqueue = m_targetDelay.GetSeconds() * m_ptc;
522 
523  if (m_minTh < targetqueue / 2.0 )
524  {
525  m_minTh = targetqueue / 2.0;
526  }
527  if (GetMode () == QUEUE_DISC_MODE_BYTES)
528  {
530  }
531 
532  // set m_maxTh to three times m_minTh [Ref: http://www.icir.org/floyd/papers/adaptiveRed.pdf]
533  m_maxTh = 3 * m_minTh;
534  }
535 
537 
538  m_qAvg = 0.0;
539  m_count = 0;
540  m_countBytes = 0;
541  m_old = 0;
542  m_idle = 1;
543 
544  double th_diff = (m_maxTh - m_minTh);
545  if (th_diff == 0)
546  {
547  th_diff = 1.0;
548  }
549  m_vA = 1.0 / th_diff;
550  m_curMaxP = 1.0 / m_lInterm;
551  m_vB = -m_minTh / th_diff;
552 
553  if (m_isGentle)
554  {
555  m_vC = (1.0 - m_curMaxP) / m_maxTh;
556  m_vD = 2.0 * m_curMaxP - 1.0;
557  }
558  m_idleTime = NanoSeconds (0);
559 
560 /*
561  * If m_qW=0, set it to a reasonable value of 1-exp(-1/C)
562  * This corresponds to choosing m_qW to be of that value for
563  * which the packet time constant -1/ln(1-m)qW) per default RTT
564  * of 100ms is an order of magnitude more than the link capacity, C.
565  *
566  * If m_qW=-1, then the queue weight is set to be a function of
567  * the bandwidth and the link propagation delay. In particular,
568  * the default RTT is assumed to be three times the link delay and
569  * transmission delay, if this gives a default RTT greater than 100 ms.
570  *
571  * If m_qW=-2, set it to a reasonable value of 1-exp(-10/C).
572  */
573  if (m_qW == 0.0)
574  {
575  m_qW = 1.0 - std::exp (-1.0 / m_ptc);
576  }
577  else if (m_qW == -1.0)
578  {
579  double rtt = 3.0 * (m_linkDelay.GetSeconds () + 1.0 / m_ptc);
580 
581  if (rtt < 0.1)
582  {
583  rtt = 0.1;
584  }
585  m_qW = 1.0 - std::exp (-1.0 / (10 * rtt * m_ptc));
586  }
587  else if (m_qW == -2.0)
588  {
589  m_qW = 1.0 - std::exp (-10.0 / m_ptc);
590  }
591 
592  if (m_bottom == 0)
593  {
594  m_bottom = 0.01;
595  // Set bottom to at most 1/W, where W is the delay-bandwidth
596  // product in packets for a connection.
597  // So W = m_linkBandwidth.GetBitRate () / (8.0 * m_meanPktSize * m_rtt.GetSeconds())
598  double bottom1 = (8.0 * m_meanPktSize * m_rtt.GetSeconds()) / m_linkBandwidth.GetBitRate();
599  if (bottom1 < m_bottom)
600  {
601  m_bottom = bottom1;
602  }
603  }
604 
605  NS_LOG_DEBUG ("\tm_delay " << m_linkDelay.GetSeconds () << "; m_isWait "
606  << m_isWait << "; m_qW " << m_qW << "; m_ptc " << m_ptc
607  << "; m_minTh " << m_minTh << "; m_maxTh " << m_maxTh
608  << "; m_isGentle " << m_isGentle << "; th_diff " << th_diff
609  << "; lInterm " << m_lInterm << "; va " << m_vA << "; cur_max_p "
610  << m_curMaxP << "; v_b " << m_vB << "; m_vC "
611  << m_vC << "; m_vD " << m_vD);
612 }
613 
614 // Updating m_curMaxP, following the pseudocode
615 // from: A Self-Configuring RED Gateway, INFOCOMM '99.
616 // They recommend m_a = 3, and m_b = 2.
617 void
619 {
620  NS_LOG_FUNCTION (this << newAve);
621 
622  if (m_minTh < newAve && newAve < m_maxTh)
623  {
625  }
626  else if (newAve < m_minTh && m_fengStatus != Below)
627  {
629  m_curMaxP = m_curMaxP / m_a;
630  }
631  else if (newAve > m_maxTh && m_fengStatus != Above)
632  {
634  m_curMaxP = m_curMaxP * m_b;
635  }
636 }
637 
638 // Update m_curMaxP to keep the average queue length within the target range.
639 void
641 {
642  NS_LOG_FUNCTION (this << newAve);
643 
644  Time now = Simulator::Now ();
645  double m_part = 0.4 * (m_maxTh - m_minTh);
646  // AIMD rule to keep target Q~1/2(m_minTh + m_maxTh)
647  if (newAve < m_minTh + m_part && m_curMaxP > m_bottom)
648  {
649  // we should increase the average queue size, so decrease m_curMaxP
651  m_lastSet = now;
652  }
653  else if (newAve > m_maxTh - m_part && m_top > m_curMaxP)
654  {
655  // we should decrease the average queue size, so increase m_curMaxP
656  double alpha = m_alpha;
657  if (alpha > 0.25 * m_curMaxP)
658  {
659  alpha = 0.25 * m_curMaxP;
660  }
661  m_curMaxP = m_curMaxP + alpha;
662  m_lastSet = now;
663  }
664 }
665 
666 // Compute the average queue size
667 double
668 RedQueueDisc::Estimator (uint32_t nQueued, uint32_t m, double qAvg, double qW)
669 {
670  NS_LOG_FUNCTION (this << nQueued << m << qAvg << qW);
671 
672  double newAve = qAvg * pow(1.0-qW, m);
673  newAve += qW * nQueued;
674 
675  Time now = Simulator::Now ();
676  if (m_isAdaptMaxP && now > m_lastSet + m_interval)
677  {
678  UpdateMaxP (newAve);
679  }
680  else if (m_isFengAdaptive)
681  {
682  UpdateMaxPFeng (newAve); // Update m_curMaxP in MIMD fashion.
683  }
684 
685  return newAve;
686 }
687 
688 // Check if packet p needs to be dropped due to probability mark
689 uint32_t
691 {
692  NS_LOG_FUNCTION (this << item << qSize);
693 
694  double prob1 = CalculatePNew ();
695  m_vProb = ModifyP (prob1, item->GetSize ());
696 
697  // Drop probability is computed, pick random number and act
698  if (m_cautious == 1)
699  {
700  /*
701  * Don't drop/mark if the instantaneous queue is much below the average.
702  * For experimental purposes only.
703  * pkts: the number of packets arriving in 50 ms
704  */
705  double pkts = m_ptc * 0.05;
706  double fraction = std::pow ((1 - m_qW), pkts);
707 
708  if ((double) qSize < fraction * m_qAvg)
709  {
710  // Queue could have been empty for 0.05 seconds
711  return 0;
712  }
713  }
714 
715  double u = m_uv->GetValue ();
716 
717  if (m_cautious == 2)
718  {
719  /*
720  * Decrease the drop probability if the instantaneous
721  * queue is much below the average.
722  * For experimental purposes only.
723  * pkts: the number of packets arriving in 50 ms
724  */
725  double pkts = m_ptc * 0.05;
726  double fraction = std::pow ((1 - m_qW), pkts);
727  double ratio = qSize / (fraction * m_qAvg);
728 
729  if (ratio < 1.0)
730  {
731  u *= 1.0 / ratio;
732  }
733  }
734 
735  if (u <= m_vProb)
736  {
737  NS_LOG_LOGIC ("u <= m_vProb; u " << u << "; m_vProb " << m_vProb);
738 
739  // DROP or MARK
740  m_count = 0;
741  m_countBytes = 0;
743 
744  return 1; // drop
745  }
746 
747  return 0; // no drop/mark
748 }
749 
750 // Returns a probability using these function parameters for the DropEarly funtion
751 double
753 {
754  NS_LOG_FUNCTION (this);
755  double p;
756 
757  if (m_isGentle && m_qAvg >= m_maxTh)
758  {
759  // p ranges from m_curMaxP to 1 as the average queue
760  // size ranges from m_maxTh to twice m_maxTh
761  p = m_vC * m_qAvg + m_vD;
762  }
763  else if (!m_isGentle && m_qAvg >= m_maxTh)
764  {
765  /*
766  * OLD: p continues to range linearly above m_curMaxP as
767  * the average queue size ranges above m_maxTh.
768  * NEW: p is set to 1.0
769  */
770  p = 1.0;
771  }
772  else
773  {
774  /*
775  * p ranges from 0 to m_curMaxP as the average queue size ranges from
776  * m_minTh to m_maxTh
777  */
778  p = m_vA * m_qAvg + m_vB;
779 
780  if (m_isNonlinear)
781  {
782  p *= p * 1.5;
783  }
784 
785  p *= m_curMaxP;
786  }
787 
788  if (p > 1.0)
789  {
790  p = 1.0;
791  }
792 
793  return p;
794 }
795 
796 // Returns a probability using these function parameters for the DropEarly funtion
797 double
798 RedQueueDisc::ModifyP (double p, uint32_t size)
799 {
800  NS_LOG_FUNCTION (this << p << size);
801  double count1 = (double) m_count;
802 
803  if (GetMode () == QUEUE_DISC_MODE_BYTES)
804  {
805  count1 = (double) (m_countBytes / m_meanPktSize);
806  }
807 
808  if (m_isWait)
809  {
810  if (count1 * p < 1.0)
811  {
812  p = 0.0;
813  }
814  else if (count1 * p < 2.0)
815  {
816  p /= (2.0 - count1 * p);
817  }
818  else
819  {
820  p = 1.0;
821  }
822  }
823  else
824  {
825  if (count1 * p < 1.0)
826  {
827  p /= (1.0 - count1 * p);
828  }
829  else
830  {
831  p = 1.0;
832  }
833  }
834 
835  if ((GetMode () == QUEUE_DISC_MODE_BYTES) && (p < 1.0))
836  {
837  p = (p * size) / m_meanPktSize;
838  }
839 
840  if (p > 1.0)
841  {
842  p = 1.0;
843  }
844 
845  return p;
846 }
847 
848 uint32_t
850 {
851  NS_LOG_FUNCTION (this);
852  if (GetMode () == QUEUE_DISC_MODE_BYTES)
853  {
854  return GetInternalQueue (0)->GetNBytes ();
855  }
856  else if (GetMode () == QUEUE_DISC_MODE_PACKETS)
857  {
858  return GetInternalQueue (0)->GetNPackets ();
859  }
860  else
861  {
862  NS_ABORT_MSG ("Unknown RED mode.");
863  }
864 }
865 
868 {
869  NS_LOG_FUNCTION (this);
870 
871  if (GetInternalQueue (0)->IsEmpty ())
872  {
873  NS_LOG_LOGIC ("Queue empty");
874  m_idle = 1;
876 
877  return 0;
878  }
879  else
880  {
881  m_idle = 0;
882  Ptr<QueueDiscItem> item = GetInternalQueue (0)->Dequeue ();
883 
884  NS_LOG_LOGIC ("Popped " << item);
885 
886  NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
887  NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
888 
889  return item;
890  }
891 }
892 
895 {
896  NS_LOG_FUNCTION (this);
897  if (GetInternalQueue (0)->IsEmpty ())
898  {
899  NS_LOG_LOGIC ("Queue empty");
900  return 0;
901  }
902 
903  Ptr<const QueueDiscItem> item = GetInternalQueue (0)->Peek ();
904 
905  NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
906  NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
907 
908  return item;
909 }
910 
911 bool
913 {
914  NS_LOG_FUNCTION (this);
915  if (GetNQueueDiscClasses () > 0)
916  {
917  NS_LOG_ERROR ("RedQueueDisc cannot have classes");
918  return false;
919  }
920 
921  if (GetNPacketFilters () > 0)
922  {
923  NS_LOG_ERROR ("RedQueueDisc cannot have packet filters");
924  return false;
925  }
926 
927  if (GetNInternalQueues () == 0)
928  {
929  // create a DropTail queue
930  Ptr<InternalQueue> queue = CreateObjectWithAttributes<DropTailQueue<QueueDiscItem> > ("Mode", EnumValue (m_mode));
932  {
933  queue->SetMaxPackets (m_queueLimit);
934  }
935  else
936  {
937  queue->SetMaxBytes (m_queueLimit);
938  }
939  AddInternalQueue (queue);
940  }
941 
942  if (GetNInternalQueues () != 1)
943  {
944  NS_LOG_ERROR ("RedQueueDisc needs 1 internal queue");
945  return false;
946  }
947 
950  {
951  NS_LOG_ERROR ("The mode of the provided queue does not match the mode set on the RedQueueDisc");
952  return false;
953  }
954 
955  if ((m_mode == QUEUE_DISC_MODE_PACKETS && GetInternalQueue (0)->GetMaxPackets () != m_queueLimit) ||
956  (m_mode == QUEUE_DISC_MODE_BYTES && GetInternalQueue (0)->GetMaxBytes () != m_queueLimit))
957  {
958  NS_LOG_ERROR ("The size of the internal queue differs from the queue disc limit");
959  return false;
960  }
961 
963  {
964  NS_LOG_ERROR ("m_isAdaptMaxP and m_isFengAdaptive cannot be simultaneously true");
965  }
966 
967  return true;
968 }
969 
970 } // namespace ns3
void SetMode(QueueDiscMode mode)
Set the operating mode of this queue disc.
bool m_isGentle
True to increase dropping prob.
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:102
uint32_t GetQueueSize(void)
Get the current value of the queue in bytes or packets.
uint32_t GetNQueueDiscClasses(void) const
Get the number of queue disc classes.
Definition: queue-disc.cc:557
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.
#define NS_ABORT_MSG(msg)
Unconditional abnormal program termination with a message.
Definition: abort.h:50
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:609
#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.
uint32_t GetNBytes(void) const
Get the amount of bytes stored by the queue disc.
Definition: queue-disc.cc:437
double GetFengAdaptiveA(void)
Get the alpha value to adapt m_curMaxP in Feng'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:687
Time m_linkDelay
Link delay.
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
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's Adaptive RED.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:201
Time MilliSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition: nstime.h:1001
QueueDiscMode GetMode(void)
Get the operating mode of this queue disc.
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's Adaptive RED.
#define NS_LOG_INFO(msg)
Use NS_LOG to output a message of level LOG_INFO.
Definition: log.h:277
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:151
A RED packet queue disc.
double m_b
Increment parameter for m_curMaxP in Feng'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.
Use number of packets for maximum queue size.
Definition: queue.h:166
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< InternalQueue > GetInternalQueue(uint32_t i) const
Get the i-th internal queue.
Definition: queue-disc.cc:492
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.
double GetSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:341
void SetQueueLimit(uint32_t lim)
Set the limit of the queue.
uint32_t GetNInternalQueues(void) const
Get the number of internal queues.
Definition: queue-disc.cc:499
void AddInternalQueue(Ptr< InternalQueue > queue)
Add an internal queue to the tail of the list of queues.
Definition: queue-disc.cc:472
Time m_idleTime
Start of current idle period.
Hold variables of type enum.
Definition: enum.h:54
AttributeValue implementation for Time.
Definition: nstime.h:1055
double GetFengAdaptiveB(void)
Get the beta value to adapt m_curMaxP in Feng's Adaptive RED.
uint32_t m_queueLimit
Queue limit in bytes / packets.
Time NanoSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition: nstime.h:1017
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
double m_vB
-m_minTh / (m_maxTh - m_minTh)
virtual void DoDispose(void)
Dispose of the object.
Definition: queue-disc.cc:371
bool m_isNonlinear
True to enable Nonlinear RED.
uint32_t GetNPacketFilters(void) const
Get the number of packet filters.
Definition: queue-disc.cc:519
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)
Use number of bytes for maximum queue disc size.
uint32_t m_idlePktSize
Avg pkt size used during idle times.
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.
QueueDiscMode
Enumeration of the modes supported in the class.
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.
Use number of bytes for maximum queue size.
Definition: queue.h:167
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:1056
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")
When m_qAvg > m_maxTh.
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
uint32_t m_old
0 when average queue first exceeds threshold
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
void SetFengAdaptiveA(double a)
Set the alpha value to adapt m_curMaxP in Feng's Adaptive RED.
QueueDiscMode m_mode
Mode (Bytes or packets)
#define NS_LOG_WARN(msg)
Use NS_LOG to output a message of level LOG_WARN.
Definition: log.h:261
AttributeValue implementation for DataRate.
Definition: data-rate.h:242
An "unforced" (random) drop.
DataRate m_linkBandwidth
Link bandwidth.
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:269
Time Seconds(double value)
Construct a Time in the indicated unit.
Definition: nstime.h:993
Time m_interval
Time interval to update m_curMaxP.
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:253
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's Adaptive RED.
bool m_isFengAdaptive
True to enable Feng'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.
virtual Ptr< const QueueDiscItem > DoPeek(void) const
This function returns a copy of the next packet the queue disc will extract.
This class can be used to hold variables of floating point type such as 'double' or 'float'...
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
a unique identifier for an interface.
Definition: type-id.h:58
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:914
double m_vProb
Prob.
Use number of packets for maximum queue disc size.
double m_maxTh
Maximum threshold for m_qAvg (bytes or packets), should be >= 2 * m_minTh.
When m_maxTh < m_qAvg < m_minTh.
When m_qAvg < m_minTh.
double m_a
Decrement parameter for m_curMaxP in Feng's Adaptive RED.
uint32_t GetNPackets(void) const
Get the number of packets stored by the queue disc.
Definition: queue-disc.cc:430
bool m_isNs1Compat
Ns-1 compatibility.