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>
25 * Random Early Detection (RED) algorithm.
27 * This implementation uses Bytes as queue size metric by default
28 * based on the Kuznetsov's implementation of Red in Linux.
29 * Therefore, only bytes as queue size metric is supported at the moment.
31 * Original RED is from
32 * Sally Floyd and Van Jacobson, "Random Early Detection Gateways for
33 * Congestion Avoidance", 1993, IEEE/ACM Transactions on Networking
38 * avg = (1-W)*avg + W*currentQueueLen
39 * W is the queue weight( chosen as 2^(-Wlog)). Decrease W for larger bursts
41 * if ( avg > maxTh) -> mark/drop packets
42 * if ( avg < minTh) -> allow packets
43 * if ( minTh < avg < maxTh) -> calculate probability for marking/dropping
46 * Pb = maxP*(avg - minTh)/(maxTh - minTh)
47 * Note: As avg varies from minTh to maxTh, Pb varies 0 to maxP
49 * Pa = Pb /(1 - count*Pb)
50 * The final marking probability Pa increases slowly as the count increases
51 * since the last marked packet
53 * maxP can be chosen s/t:
54 * maxP = (maxTh - minTh )/2^Plog
56 * To allow large bursts of L packets of size S, W can be chosen as:
57 * (see paper for details)
59 * L + 1 - minTh/S < (1-(1-W)^L)/W
73 #include "ns3/packet.h"
74 #include "ns3/queue.h"
75 #include "ns3/nstime.h"
84 * \brief A RED packet queue
86 class RedQueue : public Queue
89 typedef std::vector< uint32_t> Uint32tVector;
93 uint32_t probDrop; ///< Early probability drops
94 uint32_t probMark; ///< Early probability marks
95 uint32_t forcedDrop; ///< Forced drops, qavg > max threshold
96 uint32_t forcedMark; ///< Forced marks, qavg > max threshold
97 uint32_t pdrop; ///< Drops due to queue limits
98 uint32_t other; ///< Drops due to drop calls
102 static TypeId GetTypeId (void);
104 * \brief RedQueue Constructor
109 virtual ~RedQueue ();
112 * Enumeration of the modes supported in the class.
117 ILLEGAL, /**< Mode not set */
118 PACKETS, /**< Use number of packets for maximum queue size */
119 BYTES, /**< Use number of bytes for maximum queue size */
123 * Enumeration of RED thresholds
134 * Enumeration Marking
145 * Set the operating mode of this device.
147 * \param mode The operating mode of this device.
150 void SetMode (RedQueue::Mode mode);
153 * Get the encapsulation mode of this device.
155 * \returns The encapsulation mode of this device.
157 RedQueue::Mode GetMode (void);
160 * Get the average queue size
162 * \returns The average queue size in bytes
164 uint64_t GetAverageQueueSize (void);
168 void SetParams (uint32_t minTh, uint32_t maxTh,
169 uint32_t wLog, uint32_t pLog, uint64_t scellLog );
170 void StartIdlePeriod ();
171 void EndIdlePeriod ();
178 int CheckThresh (uint64_t avg);
179 int Processing (uint64_t avg);
180 int MarkProbability (uint64_t avg);
181 int DropPacket (Ptr<Packet> p);
183 uint64_t AvgFromIdleTime ();
184 uint64_t AvgCalc (uint32_t backlog);
186 ///< Avg = Avg*(1-W) + backlog*W
187 uint64_t AvgFromNonIdleTime (uint32_t backlog);
189 ///< burst + 1 - qmin/avpkt < (1-(1-W)^burst)/W
190 ///< this low-pass filter is used to calculate the avg queue size
191 uint32_t evalEwma (uint32_t minTh, uint32_t burst, uint32_t avpkt);
193 ///< Plog = log (prob / (qMax - qMin))
194 uint32_t evalP (uint32_t minTh, uint32_t maxTh, double prob);
196 ///< -log(1-W) * t/TxTime
197 uint32_t evalIdleDamping (uint32_t wLog, uint32_t avpkt, uint32_t rate);
199 uint32_t Rmask (uint32_t pLog);
200 uint32_t RedRandom ();
202 virtual bool DoEnqueue (Ptr<Packet> p);
203 virtual Ptr<Packet> DoDequeue (void);
204 virtual Ptr<const Packet> DoPeek (void) const;
207 std::list<Ptr<Packet> > m_packets;
211 uint32_t m_bytesInQueue;
213 ///< users' configurable options
214 uint32_t m_maxPackets;
219 * in bytes, use with burst to determine the time constant
220 * for average queue size calculations, for ewma
223 uint32_t m_minTh; ///> Min avg length threshold (bytes), should be < maxTh/2
224 uint32_t m_maxTh; ///> Max avg length threshold (bytes), should be >= 2*minTh
225 uint32_t m_rate; ///> bandwidth in bps
226 uint32_t m_wLog; ///> log(W) bits
227 uint32_t m_pLog; ///> random number bits log (P_max/(maxTh - minTh))
229 uint32_t m_scellLog; ///> cell size for idle damping
231 uint32_t m_count; ///> number of packets since last random number generation
232 uint32_t m_randNum; ///> a random number 0 ...2^Plog
234 uint64_t m_qavg; ///> average q length
239 Time m_idleStart; ///> start of current idle period
240 Uint32tVector m_sTable;
245 #endif /* RED_QUEUE_H */