1 /* Copyright (c) 2011, 2014. The SimGrid Team.
2 * All rights reserved. */
4 /* This program is free software; you can redistribute it and/or modify it
5 * under the terms of the license (GNU LGPL) which comes with this package. */
8 * Copyright (c) 2010 Regents of the University of California
10 * This program is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License version 2 as
12 * published by the Free Software Foundation;
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23 * Author: Duy Nguyen<duy@soe.ucsc.edu>
29 #include "ns3/uinteger.h"
30 #include "ns3/double.h"
31 #include "red-queue.h"
32 #include "ns3/simulator.h"
33 #include "ns3/nstime.h"
34 #include "ns3/random-variable.h"
38 NS_LOG_COMPONENT_DEFINE ("red");
40 #define RED_STATS_TABLE_SIZE 256
41 #define RED_STATS_MASK (RED_STATS_TABLE_SIZE - 1)
45 NS_OBJECT_ENSURE_REGISTERED (RedQueue);
47 TypeId RedQueue::GetTypeId (void)
49 ///< Note: these paramemters must be worked out beforehand for RED to work correctly
50 ///< How these parameters are set up can affect RED performance greatly
51 static TypeId tid = TypeId ("ns3::RedQueue")
53 .AddConstructor<RedQueue> ()
54 .AddAttribute ("Mode",
55 "Whether to use Bytes (see MaxBytes) or Packets (see MaxPackets) as the maximum queue size metric.",
56 EnumValue (BYTES), ///> currently supports BYTES only
57 MakeEnumAccessor (&RedQueue::SetMode),
58 MakeEnumChecker (BYTES, "Bytes",
60 .AddAttribute ("MaxPackets",
61 "The maximum number of packets accepted by this RedQueue.",
63 MakeUintegerAccessor (&RedQueue::m_maxPackets),
64 MakeUintegerChecker<uint32_t> ())
65 .AddAttribute ("MaxBytes",
66 "The maximum number of bytes accepted by this RedQueue.",
67 UintegerValue (100000),
68 MakeUintegerAccessor (&RedQueue::m_maxBytes),
69 MakeUintegerChecker<uint32_t> ())
70 .AddAttribute ("m_burst",
71 "maximum number of m_burst packets accepted by this queue",
72 UintegerValue (6), ///> bursts must be > minTh/avpkt
73 MakeUintegerAccessor (&RedQueue::m_burst),
74 MakeUintegerChecker<uint32_t> ())
75 .AddAttribute ("m_avPkt",
76 "In bytes, use with m_burst to determine the time constant for average queue size calculations",
77 UintegerValue (1024), ///> average packet size
78 MakeUintegerAccessor (&RedQueue::m_avPkt),
79 MakeUintegerChecker<uint32_t> ())
80 .AddAttribute ("m_minTh",
81 "Average queue size at which marking becomes a m_prob",
82 UintegerValue (5120), ///> in bytes 1024x5
83 MakeUintegerAccessor (&RedQueue::m_minTh),
84 MakeUintegerChecker<uint32_t> ())
85 .AddAttribute ("m_maxTh",
86 "Maximal marking m_prob, should be at least twice min to prevent synchronous retransmits",
87 UintegerValue (15360), ///> in bytes 1024x15
88 MakeUintegerAccessor (&RedQueue::m_maxTh),
89 MakeUintegerChecker<uint32_t> ())
90 .AddAttribute ("m_rate",
91 "this m_rate is used for calculating the average queue size after some idle time.",
92 UintegerValue (1500000), ///> in bps, should be set to bandwidth of interface
93 MakeUintegerAccessor (&RedQueue::m_rate),
94 MakeUintegerChecker<uint64_t> ())
95 .AddAttribute ("m_prob",
96 "Probability for marking, suggested values are 0.01 and 0.02",
98 MakeDoubleAccessor (&RedQueue::m_prob),
99 MakeDoubleChecker <double> ())
105 RedQueue::RedQueue ()
117 m_initialized (false)
120 m_sTable = Uint32tVector (RED_STATS_TABLE_SIZE);
124 RedQueue::~RedQueue ()
126 NS_LOG_FUNCTION_NOARGS ();
130 RedQueue::SetMode (enum Mode mode)
132 NS_LOG_FUNCTION (mode);
137 RedQueue::GetMode (void)
143 RedQueue::GetAverageQueueSize (void)
151 * Given minimum threshold min_th and that we wish to allow bursts of L packets
152 * Then Wq should be chosen to satisfy avg_L < min_th
153 * L + 1 + [(1-Wq)^(L+1) - 1]/ Wq < min_th
154 * L + 1 - min_th < [1 - (1-Wq)^(L+1)]/Wq
155 * i.e. given min_th 5, L=50, necessary that Wq <= 0.0042
158 * burst + 1 - minTh/avPkt < (1-(1-W)^burst)/W
159 * this low-pass filter is used to calculate the avg queue size
163 RedQueue::evalEwma (uint32_t minTh, uint32_t burst, uint32_t avpkt)
165 NS_LOG_FUNCTION (this);
174 ///< Note: bursts must be larger than minTh/avpkt for it to work
175 temp = (double)burst + 1 - (double)minTh / avpkt;
177 NS_LOG_DEBUG ( "\t temp =" << temp);
181 NS_LOG_DEBUG ("\tFailed to calculate EWMA constant");
189 * wlog =4 , W = .0625
190 * wlog =5 , W = .03125
191 * wlog =6 , W = .015625
192 * wlog =7 , W = .0078125
193 * wlog =8 , W = .00390625
194 * wlog =9 , W = .001953125
195 * wlog =10, W = .0009765625
197 for (wlog = 1; wlog < 32; wlog++, W /= 2)
199 if (temp <= (1 - pow (1 - W, burst)) / W )
201 NS_LOG_DEBUG ("\t wlog=" << wlog);
206 NS_LOG_DEBUG ("\tFailed to calculate EWMA constant");
212 * Plog = log (prob / (maxTh -minTh) );
214 * Paper says: When a packet arrives at the gateway and the average queue size
215 * is between min_th and max_th, the initial packet marking probability is:
218 * C1 = maxP/(max_th - mint_th)
219 * C2 = maxP*min_th/(max_th - mint_th)
220 * maxP could be chosen so that C1 a power of two
223 RedQueue::evalP (uint32_t minTh, uint32_t maxTh, double prob)
225 NS_LOG_FUNCTION (this);
227 uint32_t i = maxTh - minTh ;
231 NS_LOG_DEBUG ("maxTh - minTh = 0");
237 ///< It returns the index that makes C1 a power of two
238 for (i = 0; i < 32; i++)
250 NS_LOG_DEBUG ("i >= 32, this shouldn't happen");
254 NS_LOG_DEBUG ("\t i(makes C1 power of two)=" << i);
260 * avg = avg*(1-W)^m where m = t/xmitTime
262 * m_sTable[ t/2^cellLog] = -log(1-W) * t/xmitTime
263 * m_sTable[ t >> cellLog]= -log(1-W) * t/xmitTime
265 * t is converted to t/2^cellLog for storage in the table
266 * find out what is cellLog and return it
270 RedQueue::evalIdleDamping (uint32_t wLog, uint32_t avpkt, uint32_t bps)
272 NS_LOG_FUNCTION (this);
274 ///> in microsecond ticks: 1 sec = 1000000 microsecond ticks
275 double xmitTime = ((double) avpkt / bps) * 1000000;
277 ///> -log(1 - 1/2^wLog) / xmitTime
278 ///> note W = 1/2^wLog
279 double wLogTemp = -log (1.0 - 1.0 / (1 << wLog)) / xmitTime;
282 ///> the maximum allow idle time
283 double maxTime = 31 / wLogTemp;
285 NS_LOG_DEBUG ("\t xmitTime=" << xmitTime << " wLogTemp=" << wLogTemp
286 << " maxTime=" << maxTime);
291 for (cLog = 0; cLog < 32; cLog++)
294 ///> maxTime < 512* 2^cLog
295 ///> finds the cLog that's able to cover this maxTime
296 if (maxTime / (1 << cLog) < 512)
309 for (i = 1; i < 255; i++)
311 ///> wLogTemp * i * 2^cLog
312 m_sTable[i] = (i << cLog) * wLogTemp;
315 if (m_sTable[i] > 31)
323 NS_LOG_DEBUG ("\t cLog=" << cLog);
330 RedQueue::Rmask (uint32_t pLog)
332 ///> ~OUL creates a 32 bit mask
334 return pLog < 32 ? ((1 << pLog) - 1) : ~0UL;
340 RedQueue::SetParams (uint32_t minTh, uint32_t maxTh,
341 uint32_t wLog, uint32_t pLog, uint64_t scellLog)
343 NS_LOG_FUNCTION (this);
351 m_rmask = Rmask (pLog);
352 m_scellLog = scellLog;
353 m_scellMax = (255 << m_scellLog);
355 NS_LOG_DEBUG ("\t m_wLog" << m_wLog << " m_pLog" << m_pLog << " m_scellLog" << m_scellLog
356 << " m_minTh" << m_minTh << " m_maxTh" << m_maxTh
357 << " rmask=" << m_rmask << " m_scellMax=" << m_scellMax);
361 RedQueue::IsIdling ()
363 NS_LOG_FUNCTION_NOARGS ();
366 if ( m_idleStart.GetNanoSeconds () != 0)
368 NS_LOG_DEBUG ("\t IsIdling");
371 return m_idleStart.GetNanoSeconds () != 0;
374 RedQueue::StartIdlePeriod ()
376 NS_LOG_FUNCTION_NOARGS ();
378 m_idleStart = Simulator::Now ();
381 RedQueue::EndIdlePeriod ()
383 NS_LOG_FUNCTION_NOARGS ();
385 m_idleStart = NanoSeconds (0);
391 NS_LOG_FUNCTION_NOARGS ();
402 * m is the number of pkts that might have been transmitted by the gateway
403 * during the time that the queue was free
404 * s is a typical transmission for a packet
406 * m = idletime / (average pkt size / bandwidth)
410 * We need to precompute a table for this calculation because of the exp power
414 RedQueue::AvgFromIdleTime ()
416 NS_LOG_FUNCTION_NOARGS ();
421 idleTime = ns3::Time(Simulator::Now() - m_idleStart).GetMicroSeconds();
422 //idleTime = RedTimeToInteger (Simulator::Now() - m_idleStart, Time::US);
424 if (idleTime > m_scellMax)
426 idleTime = m_scellMax;
429 NS_LOG_DEBUG ("\t idleTime=" << idleTime);
432 shift = m_sTable [(idleTime >> m_scellLog) & RED_STATS_MASK];
436 //std::cout << "shift " << m_qavg << "=>" << (m_qavg >> shift) << std::endl;
437 return m_qavg >> shift;
441 idleTime = (m_qavg * idleTime) >> m_scellLog;
444 NS_LOG_DEBUG ("\t idleus=" << idleTime);
446 if (idleTime < (m_qavg / 2))
448 //std::cout <<"idleus " << m_qavg << " - " << idleus << " = " << (m_qavg-idleus) << std::endl;
449 return m_qavg - idleTime;
453 //std:: cout <<"half " << m_qavg << "=>" << (m_qavg/2) << std::endl;
454 return (m_qavg / 2) ;
460 RedQueue::AvgFromNonIdleTime (uint32_t backlog)
462 NS_LOG_FUNCTION (this << backlog);
464 NS_LOG_DEBUG ("qavg " << m_qavg);
465 NS_LOG_DEBUG ("backlog" << backlog);
468 * This is basically EWMA
469 * m_qavg = q_avg*(1-W) + backlog*W
470 * m_qavg = q_avg + W(backlog - q_avg)
473 return m_qavg + (backlog - (m_qavg >> m_wLog));
477 RedQueue::AvgCalc (uint32_t backlog)
479 NS_LOG_FUNCTION (this << backlog);
485 qtemp = AvgFromNonIdleTime (backlog);
486 NS_LOG_DEBUG ("NonIdle Avg " << qtemp);
487 //std::cout <<"n "<< qtemp << std::endl;
492 qtemp = AvgFromIdleTime ();
493 NS_LOG_DEBUG ("Idle Avg" << qtemp);
494 //std::cout <<"i "<< qtemp << std::endl;
500 RedQueue::CheckThresh (uint64_t avg)
503 NS_LOG_FUNCTION (this << avg);
504 NS_LOG_DEBUG ("\t check threshold: min " << m_minTh << " max" << m_maxTh);
508 return BELOW_MIN_THRESH;
510 else if (avg >= m_maxTh)
512 return ABOVE_MAX_THRESH;
516 return BETWEEN_THRESH;
520 RedQueue::RedRandom ()
522 NS_LOG_FUNCTION_NOARGS ();
524 ///> obtain a random u32 number
525 ///> return m_rmask & ran.GetInteger ();
527 return m_rmask & rand ();
530 RedQueue::MarkProbability (uint64_t avg)
532 NS_LOG_FUNCTION (this << avg);
533 NS_LOG_DEBUG ("\t m_randNum " << m_randNum);
534 NS_LOG_DEBUG ("\t right\t" << m_randNum);
535 NS_LOG_DEBUG ("\t left\t" << ((avg - m_minTh)*m_count));
537 ///> max_P* (qavg - qth_min)/(qth_max-qth_min) < rnd/qcount
538 //return !((avg - m_minTh ) * m_count < m_randNum);
540 return !((avg - m_minTh )* m_count < m_randNum);
544 RedQueue::Processing (uint64_t qavg)
547 NS_LOG_FUNCTION (this << "qavg" << qavg << " m_minTh" << m_minTh << " m_maxTh" << m_maxTh);
549 switch (CheckThresh (qavg))
551 case BELOW_MIN_THRESH:
552 NS_LOG_DEBUG ("\t below threshold ");
558 NS_LOG_DEBUG ("\t between threshold ");
562 NS_LOG_DEBUG ("\t check Mark Prob");
563 if (MarkProbability (qavg))
566 m_randNum = RedRandom ();
568 NS_LOG_DEBUG ("\t Marked Will Drop " << m_qavg);
572 NS_LOG_DEBUG ("\t Marked Will Save " << m_qavg);
576 m_randNum = RedRandom ();
580 case ABOVE_MAX_THRESH:
582 NS_LOG_DEBUG ("\t above threshold ");
588 NS_LOG_DEBUG ("BUG HERE\n");
594 RedQueue::DoEnqueue (Ptr<Packet> p)
596 NS_LOG_FUNCTION (this << p);
598 if (m_mode == PACKETS && (m_packets.size () >= m_maxPackets))
600 NS_LOG_LOGIC ("Queue full (at max packets) -- droppping pkt");
605 if (m_mode == BYTES && (m_bytesInQueue + p->GetSize () >= m_maxBytes))
607 NS_LOG_LOGIC ("Queue full (packet would exceed max bytes) -- droppping pkt");
614 // making sure all the variables are initialized ok
615 NS_LOG_DEBUG ("\t m_maxPackets" << m_maxPackets
616 << " m_maxBytes" << m_maxBytes
617 << " m_burst" << m_burst << " m_avPkt" << m_avPkt
618 << " m_minTh" << m_minTh << " m_maxTh" << m_maxTh
619 << " m_rate" << m_rate << " m_prob" << m_prob);
621 m_wLog = evalEwma (m_minTh, m_burst, m_avPkt);
622 m_pLog = evalP (m_minTh, m_maxTh, m_prob);
623 m_scellLog = evalIdleDamping (m_wLog, m_avPkt, m_rate);
625 SetParams (m_minTh, m_maxTh, m_wLog, m_pLog, m_scellLog);
627 // srand((unsigned)time(0));
628 m_initialized = true;
633 if (GetMode () == BYTES)
635 m_qavg = AvgCalc (m_bytesInQueue);
637 else if (GetMode () == PACKETS)
640 // m_qavg = AvgCalc (m_packets.size ());
643 NS_LOG_DEBUG ("\t bytesInQueue " << m_bytesInQueue << "\tQavg " << m_qavg);
644 NS_LOG_DEBUG ("\t packetsInQueue " << m_packets.size () << "\tQavg " << m_qavg);
652 switch (Processing (m_qavg) )
658 NS_LOG_DEBUG ("\t Dropping due to Prob Mark " << m_qavg);
665 NS_LOG_DEBUG ("\t Dropping due to Hard Mark " << m_qavg);
666 m_stats.forcedMark++;
673 m_bytesInQueue += p->GetSize ();
674 m_packets.push_back (p);
676 NS_LOG_LOGIC ("Number packets " << m_packets.size ());
677 NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
683 RedQueue::DoDequeue (void)
685 NS_LOG_FUNCTION (this);
687 if (m_packets.empty ())
689 NS_LOG_LOGIC ("Queue empty");
693 Ptr<Packet> p = m_packets.front ();
694 m_packets.pop_front ();
695 m_bytesInQueue -= p->GetSize ();
697 NS_LOG_LOGIC ("Popped " << p);
699 NS_LOG_LOGIC ("Number packets " << m_packets.size ());
700 NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
702 if (m_bytesInQueue <= 0 && !IsIdling ())
710 ///> just for completeness
711 /// m_packets.remove (p) also works
713 RedQueue::DropPacket (Ptr<Packet> p)
716 NS_LOG_FUNCTION (this << p);
718 NS_LOG_DEBUG ("\t Dropping Packet p");
720 std::list<Ptr<Packet> >::iterator iter;
723 for (iter = m_packets.begin(); iter != m_packets.end(); ++iter)
727 packetSize= p->GetSize ();
728 m_packets.erase(iter);
729 m_bytesInQueue -= packetSize;
743 RedQueue::DoPeek (void) const
745 NS_LOG_FUNCTION (this);
747 if (m_packets.empty ())
749 NS_LOG_LOGIC ("Queue empty");
753 Ptr<Packet> p = m_packets.front ();
755 NS_LOG_LOGIC ("Number packets " << m_packets.size ());
756 NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
762 RedQueue::PrintTable ()
764 NS_LOG_FUNCTION_NOARGS ();
766 for (uint32_t i = 0; i < RED_STATS_TABLE_SIZE; i++)
768 std::cout << m_sTable[i] << " ";
770 std::cout << std::endl;