1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
3 * Copyright (c) 2010 Regents of the University of California
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;
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.
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
18 * Author: Duy Nguyen<duy@soe.ucsc.edu>
24 #include "ns3/uinteger.h"
25 #include "ns3/double.h"
26 #include "red-queue.h"
27 #include "ns3/simulator.h"
28 #include "ns3/nstime.h"
29 #include "ns3/random-variable.h"
33 NS_LOG_COMPONENT_DEFINE ("red");
35 #define RED_STATS_TABLE_SIZE 256
36 #define RED_STATS_MASK (RED_STATS_TABLE_SIZE - 1)
40 NS_OBJECT_ENSURE_REGISTERED (RedQueue);
42 TypeId RedQueue::GetTypeId (void)
44 ///< Note: these paramemters must be worked out beforehand for RED to work correctly
45 ///< How these parameters are set up can affect RED performance greatly
46 static TypeId tid = TypeId ("ns3::RedQueue")
48 .AddConstructor<RedQueue> ()
49 .AddAttribute ("Mode",
50 "Whether to use Bytes (see MaxBytes) or Packets (see MaxPackets) as the maximum queue size metric.",
51 EnumValue (BYTES), ///> currently supports BYTES only
52 MakeEnumAccessor (&RedQueue::SetMode),
53 MakeEnumChecker (BYTES, "Bytes",
55 .AddAttribute ("MaxPackets",
56 "The maximum number of packets accepted by this RedQueue.",
58 MakeUintegerAccessor (&RedQueue::m_maxPackets),
59 MakeUintegerChecker<uint32_t> ())
60 .AddAttribute ("MaxBytes",
61 "The maximum number of bytes accepted by this RedQueue.",
62 UintegerValue (100000),
63 MakeUintegerAccessor (&RedQueue::m_maxBytes),
64 MakeUintegerChecker<uint32_t> ())
65 .AddAttribute ("m_burst",
66 "maximum number of m_burst packets accepted by this queue",
67 UintegerValue (6), ///> bursts must be > minTh/avpkt
68 MakeUintegerAccessor (&RedQueue::m_burst),
69 MakeUintegerChecker<uint32_t> ())
70 .AddAttribute ("m_avPkt",
71 "In bytes, use with m_burst to determine the time constant for average queue size calculations",
72 UintegerValue (1024), ///> average packet size
73 MakeUintegerAccessor (&RedQueue::m_avPkt),
74 MakeUintegerChecker<uint32_t> ())
75 .AddAttribute ("m_minTh",
76 "Average queue size at which marking becomes a m_prob",
77 UintegerValue (5120), ///> in bytes 1024x5
78 MakeUintegerAccessor (&RedQueue::m_minTh),
79 MakeUintegerChecker<uint32_t> ())
80 .AddAttribute ("m_maxTh",
81 "Maximal marking m_prob, should be at least twice min to prevent synchronous retransmits",
82 UintegerValue (15360), ///> in bytes 1024x15
83 MakeUintegerAccessor (&RedQueue::m_maxTh),
84 MakeUintegerChecker<uint32_t> ())
85 .AddAttribute ("m_rate",
86 "this m_rate is used for calculating the average queue size after some idle time.",
87 UintegerValue (1500000), ///> in bps, should be set to bandwidth of interface
88 MakeUintegerAccessor (&RedQueue::m_rate),
89 MakeUintegerChecker<uint64_t> ())
90 .AddAttribute ("m_prob",
91 "Probability for marking, suggested values are 0.01 and 0.02",
93 MakeDoubleAccessor (&RedQueue::m_prob),
94 MakeDoubleChecker <double> ())
100 RedQueue::RedQueue ()
112 m_initialized (false)
115 m_sTable = Uint32tVector (RED_STATS_TABLE_SIZE);
119 RedQueue::~RedQueue ()
121 NS_LOG_FUNCTION_NOARGS ();
125 RedQueue::SetMode (enum Mode mode)
127 NS_LOG_FUNCTION (mode);
132 RedQueue::GetMode (void)
138 RedQueue::GetAverageQueueSize (void)
146 * Given minimum threshold min_th and that we wish to allow bursts of L packets
147 * Then Wq should be chosen to satisfy avg_L < min_th
148 * L + 1 + [(1-Wq)^(L+1) - 1]/ Wq < min_th
149 * L + 1 - min_th < [1 - (1-Wq)^(L+1)]/Wq
150 * i.e. given min_th 5, L=50, necessary that Wq <= 0.0042
153 * burst + 1 - minTh/avPkt < (1-(1-W)^burst)/W
154 * this low-pass filter is used to calculate the avg queue size
158 RedQueue::evalEwma (uint32_t minTh, uint32_t burst, uint32_t avpkt)
160 NS_LOG_FUNCTION (this);
169 ///< Note: bursts must be larger than minTh/avpkt for it to work
170 temp = (double)burst + 1 - (double)minTh / avpkt;
172 NS_LOG_DEBUG ( "\t temp =" << temp);
176 NS_LOG_DEBUG ("\tFailed to calculate EWMA constant");
184 * wlog =4 , W = .0625
185 * wlog =5 , W = .03125
186 * wlog =6 , W = .015625
187 * wlog =7 , W = .0078125
188 * wlog =8 , W = .00390625
189 * wlog =9 , W = .001953125
190 * wlog =10, W = .0009765625
192 for (wlog = 1; wlog < 32; wlog++, W /= 2)
194 if (temp <= (1 - pow (1 - W, burst)) / W )
196 NS_LOG_DEBUG ("\t wlog=" << wlog);
201 NS_LOG_DEBUG ("\tFailed to calculate EWMA constant");
207 * Plog = log (prob / (maxTh -minTh) );
209 * Paper says: When a packet arrives at the gateway and the average queue size
210 * is between min_th and max_th, the initial packet marking probability is:
213 * C1 = maxP/(max_th - mint_th)
214 * C2 = maxP*min_th/(max_th - mint_th)
215 * maxP could be chosen so that C1 a power of two
218 RedQueue::evalP (uint32_t minTh, uint32_t maxTh, double prob)
220 NS_LOG_FUNCTION (this);
222 uint32_t i = maxTh - minTh ;
226 NS_LOG_DEBUG ("maxTh - minTh = 0");
232 ///< It returns the index that makes C1 a power of two
233 for (i = 0; i < 32; i++)
245 NS_LOG_DEBUG ("i >= 32, this shouldn't happen");
249 NS_LOG_DEBUG ("\t i(makes C1 power of two)=" << i);
255 * avg = avg*(1-W)^m where m = t/xmitTime
257 * m_sTable[ t/2^cellLog] = -log(1-W) * t/xmitTime
258 * m_sTable[ t >> cellLog]= -log(1-W) * t/xmitTime
260 * t is converted to t/2^cellLog for storage in the table
261 * find out what is cellLog and return it
265 RedQueue::evalIdleDamping (uint32_t wLog, uint32_t avpkt, uint32_t bps)
267 NS_LOG_FUNCTION (this);
269 ///> in microsecond ticks: 1 sec = 1000000 microsecond ticks
270 double xmitTime = ((double) avpkt / bps) * 1000000;
272 ///> -log(1 - 1/2^wLog) / xmitTime
273 ///> note W = 1/2^wLog
274 double wLogTemp = -log (1.0 - 1.0 / (1 << wLog)) / xmitTime;
277 ///> the maximum allow idle time
278 double maxTime = 31 / wLogTemp;
280 NS_LOG_DEBUG ("\t xmitTime=" << xmitTime << " wLogTemp=" << wLogTemp
281 << " maxTime=" << maxTime);
286 for (cLog = 0; cLog < 32; cLog++)
289 ///> maxTime < 512* 2^cLog
290 ///> finds the cLog that's able to cover this maxTime
291 if (maxTime / (1 << cLog) < 512)
304 for (i = 1; i < 255; i++)
306 ///> wLogTemp * i * 2^cLog
307 m_sTable[i] = (i << cLog) * wLogTemp;
310 if (m_sTable[i] > 31)
318 NS_LOG_DEBUG ("\t cLog=" << cLog);
325 RedQueue::Rmask (uint32_t pLog)
327 ///> ~OUL creates a 32 bit mask
329 return pLog < 32 ? ((1 << pLog) - 1) : ~0UL;
335 RedQueue::SetParams (uint32_t minTh, uint32_t maxTh,
336 uint32_t wLog, uint32_t pLog, uint64_t scellLog)
338 NS_LOG_FUNCTION (this);
346 m_rmask = Rmask (pLog);
347 m_scellLog = scellLog;
348 m_scellMax = (255 << m_scellLog);
350 NS_LOG_DEBUG ("\t m_wLog" << m_wLog << " m_pLog" << m_pLog << " m_scellLog" << m_scellLog
351 << " m_minTh" << m_minTh << " m_maxTh" << m_maxTh
352 << " rmask=" << m_rmask << " m_scellMax=" << m_scellMax);
356 RedQueue::IsIdling ()
358 NS_LOG_FUNCTION_NOARGS ();
361 if ( m_idleStart.GetNanoSeconds () != 0)
363 NS_LOG_DEBUG ("\t IsIdling");
366 return m_idleStart.GetNanoSeconds () != 0;
369 RedQueue::StartIdlePeriod ()
371 NS_LOG_FUNCTION_NOARGS ();
373 m_idleStart = Simulator::Now ();
376 RedQueue::EndIdlePeriod ()
378 NS_LOG_FUNCTION_NOARGS ();
380 m_idleStart = NanoSeconds (0);
386 NS_LOG_FUNCTION_NOARGS ();
397 * m is the number of pkts that might have been transmitted by the gateway
398 * during the time that the queue was free
399 * s is a typical transmission for a packet
401 * m = idletime / (average pkt size / bandwidth)
405 * We need to precompute a table for this calculation because of the exp power
409 RedQueue::AvgFromIdleTime ()
411 NS_LOG_FUNCTION_NOARGS ();
416 idleTime = ns3::Time(Simulator::Now() - m_idleStart).GetMicroSeconds();
417 //idleTime = RedTimeToInteger (Simulator::Now() - m_idleStart, Time::US);
419 if (idleTime > m_scellMax)
421 idleTime = m_scellMax;
424 NS_LOG_DEBUG ("\t idleTime=" << idleTime);
427 shift = m_sTable [(idleTime >> m_scellLog) & RED_STATS_MASK];
431 //std::cout << "shift " << m_qavg << "=>" << (m_qavg >> shift) << std::endl;
432 return m_qavg >> shift;
436 idleTime = (m_qavg * idleTime) >> m_scellLog;
439 NS_LOG_DEBUG ("\t idleus=" << idleTime);
441 if (idleTime < (m_qavg / 2))
443 //std::cout <<"idleus " << m_qavg << " - " << idleus << " = " << (m_qavg-idleus) << std::endl;
444 return m_qavg - idleTime;
448 //std:: cout <<"half " << m_qavg << "=>" << (m_qavg/2) << std::endl;
449 return (m_qavg / 2) ;
455 RedQueue::AvgFromNonIdleTime (uint32_t backlog)
457 NS_LOG_FUNCTION (this << backlog);
459 NS_LOG_DEBUG ("qavg " << m_qavg);
460 NS_LOG_DEBUG ("backlog" << backlog);
463 * This is basically EWMA
464 * m_qavg = q_avg*(1-W) + backlog*W
465 * m_qavg = q_avg + W(backlog - q_avg)
468 return m_qavg + (backlog - (m_qavg >> m_wLog));
472 RedQueue::AvgCalc (uint32_t backlog)
474 NS_LOG_FUNCTION (this << backlog);
480 qtemp = AvgFromNonIdleTime (backlog);
481 NS_LOG_DEBUG ("NonIdle Avg " << qtemp);
482 //std::cout <<"n "<< qtemp << std::endl;
487 qtemp = AvgFromIdleTime ();
488 NS_LOG_DEBUG ("Idle Avg" << qtemp);
489 //std::cout <<"i "<< qtemp << std::endl;
495 RedQueue::CheckThresh (uint64_t avg)
498 NS_LOG_FUNCTION (this << avg);
499 NS_LOG_DEBUG ("\t check threshold: min " << m_minTh << " max" << m_maxTh);
503 return BELOW_MIN_THRESH;
505 else if (avg >= m_maxTh)
507 return ABOVE_MAX_THRESH;
511 return BETWEEN_THRESH;
515 RedQueue::RedRandom ()
517 NS_LOG_FUNCTION_NOARGS ();
519 ///> obtain a random u32 number
520 ///> return m_rmask & ran.GetInteger ();
522 return m_rmask & rand ();
525 RedQueue::MarkProbability (uint64_t avg)
527 NS_LOG_FUNCTION (this << avg);
528 NS_LOG_DEBUG ("\t m_randNum " << m_randNum);
529 NS_LOG_DEBUG ("\t right\t" << m_randNum);
530 NS_LOG_DEBUG ("\t left\t" << ((avg - m_minTh)*m_count));
532 ///> max_P* (qavg - qth_min)/(qth_max-qth_min) < rnd/qcount
533 //return !((avg - m_minTh ) * m_count < m_randNum);
535 return !((avg - m_minTh )* m_count < m_randNum);
539 RedQueue::Processing (uint64_t qavg)
542 NS_LOG_FUNCTION (this << "qavg" << qavg << " m_minTh" << m_minTh << " m_maxTh" << m_maxTh);
544 switch (CheckThresh (qavg))
546 case BELOW_MIN_THRESH:
547 NS_LOG_DEBUG ("\t below threshold ");
553 NS_LOG_DEBUG ("\t between threshold ");
557 NS_LOG_DEBUG ("\t check Mark Prob");
558 if (MarkProbability (qavg))
561 m_randNum = RedRandom ();
563 NS_LOG_DEBUG ("\t Marked Will Drop " << m_qavg);
567 NS_LOG_DEBUG ("\t Marked Will Save " << m_qavg);
571 m_randNum = RedRandom ();
575 case ABOVE_MAX_THRESH:
577 NS_LOG_DEBUG ("\t above threshold ");
583 NS_LOG_DEBUG ("BUG HERE\n");
589 RedQueue::DoEnqueue (Ptr<Packet> p)
591 NS_LOG_FUNCTION (this << p);
593 if (m_mode == PACKETS && (m_packets.size () >= m_maxPackets))
595 NS_LOG_LOGIC ("Queue full (at max packets) -- droppping pkt");
600 if (m_mode == BYTES && (m_bytesInQueue + p->GetSize () >= m_maxBytes))
602 NS_LOG_LOGIC ("Queue full (packet would exceed max bytes) -- droppping pkt");
609 // making sure all the variables are initialized ok
610 NS_LOG_DEBUG ("\t m_maxPackets" << m_maxPackets
611 << " m_maxBytes" << m_maxBytes
612 << " m_burst" << m_burst << " m_avPkt" << m_avPkt
613 << " m_minTh" << m_minTh << " m_maxTh" << m_maxTh
614 << " m_rate" << m_rate << " m_prob" << m_prob);
616 m_wLog = evalEwma (m_minTh, m_burst, m_avPkt);
617 m_pLog = evalP (m_minTh, m_maxTh, m_prob);
618 m_scellLog = evalIdleDamping (m_wLog, m_avPkt, m_rate);
620 SetParams (m_minTh, m_maxTh, m_wLog, m_pLog, m_scellLog);
622 // srand((unsigned)time(0));
623 m_initialized = true;
628 if (GetMode () == BYTES)
630 m_qavg = AvgCalc (m_bytesInQueue);
632 else if (GetMode () == PACKETS)
635 // m_qavg = AvgCalc (m_packets.size ());
638 NS_LOG_DEBUG ("\t bytesInQueue " << m_bytesInQueue << "\tQavg " << m_qavg);
639 NS_LOG_DEBUG ("\t packetsInQueue " << m_packets.size () << "\tQavg " << m_qavg);
647 switch (Processing (m_qavg) )
653 NS_LOG_DEBUG ("\t Dropping due to Prob Mark " << m_qavg);
660 NS_LOG_DEBUG ("\t Dropping due to Hard Mark " << m_qavg);
661 m_stats.forcedMark++;
668 m_bytesInQueue += p->GetSize ();
669 m_packets.push_back (p);
671 NS_LOG_LOGIC ("Number packets " << m_packets.size ());
672 NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
678 RedQueue::DoDequeue (void)
680 NS_LOG_FUNCTION (this);
682 if (m_packets.empty ())
684 NS_LOG_LOGIC ("Queue empty");
688 Ptr<Packet> p = m_packets.front ();
689 m_packets.pop_front ();
690 m_bytesInQueue -= p->GetSize ();
692 NS_LOG_LOGIC ("Popped " << p);
694 NS_LOG_LOGIC ("Number packets " << m_packets.size ());
695 NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
697 if (m_bytesInQueue <= 0 && !IsIdling ())
705 ///> just for completeness
706 /// m_packets.remove (p) also works
708 RedQueue::DropPacket (Ptr<Packet> p)
711 NS_LOG_FUNCTION (this << p);
713 NS_LOG_DEBUG ("\t Dropping Packet p");
715 std::list<Ptr<Packet> >::iterator iter;
718 for (iter = m_packets.begin(); iter != m_packets.end(); ++iter)
722 packetSize= p->GetSize ();
723 m_packets.erase(iter);
724 m_bytesInQueue -= packetSize;
738 RedQueue::DoPeek (void) const
740 NS_LOG_FUNCTION (this);
742 if (m_packets.empty ())
744 NS_LOG_LOGIC ("Queue empty");
748 Ptr<Packet> p = m_packets.front ();
750 NS_LOG_LOGIC ("Number packets " << m_packets.size ());
751 NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
757 RedQueue::PrintTable ()
759 NS_LOG_FUNCTION_NOARGS ();
761 for (uint32_t i = 0; i < RED_STATS_TABLE_SIZE; i++)
763 std::cout << m_sTable[i] << " ";
765 std::cout << std::endl;