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>
20 * Random Early Detection (RED) algorithm.
22 * This implementation uses Bytes as queue size metric by default
23 * based on the Kuznetsov's implementation of Red in Linux.
24 * Therefore, only bytes as queue size metric is supported at the moment.
26 * Original RED is from
27 * Sally Floyd and Van Jacobson, "Random Early Detection Gateways for
28 * Congestion Avoidance", 1993, IEEE/ACM Transactions on Networking
33 * avg = (1-W)*avg + W*currentQueueLen
34 * W is the queue weight( chosen as 2^(-Wlog)). Decrease W for larger bursts
36 * if ( avg > maxTh) -> mark/drop packets
37 * if ( avg < minTh) -> allow packets
38 * if ( minTh < avg < maxTh) -> calculate probability for marking/dropping
41 * Pb = maxP*(avg - minTh)/(maxTh - minTh)
42 * Note: As avg varies from minTh to maxTh, Pb varies 0 to maxP
44 * Pa = Pb /(1 - count*Pb)
45 * The final marking probability Pa increases slowly as the count increases
46 * since the last marked packet
48 * maxP can be chosen s/t:
49 * maxP = (maxTh - minTh )/2^Plog
51 * To allow large bursts of L packets of size S, W can be chosen as:
52 * (see paper for details)
54 * L + 1 - minTh/S < (1-(1-W)^L)/W
68 #include "ns3/packet.h"
69 #include "ns3/queue.h"
70 #include "ns3/nstime.h"
79 * \brief A RED packet queue
81 class RedQueue : public Queue
84 typedef std::vector< uint32_t> Uint32tVector;
88 uint32_t probDrop; ///< Early probability drops
89 uint32_t probMark; ///< Early probability marks
90 uint32_t forcedDrop; ///< Forced drops, qavg > max threshold
91 uint32_t forcedMark; ///< Forced marks, qavg > max threshold
92 uint32_t pdrop; ///< Drops due to queue limits
93 uint32_t other; ///< Drops due to drop calls
97 static TypeId GetTypeId (void);
99 * \brief RedQueue Constructor
104 virtual ~RedQueue ();
107 * Enumeration of the modes supported in the class.
112 ILLEGAL, /**< Mode not set */
113 PACKETS, /**< Use number of packets for maximum queue size */
114 BYTES, /**< Use number of bytes for maximum queue size */
118 * Enumeration of RED thresholds
129 * Enumeration Marking
140 * Set the operating mode of this device.
142 * \param mode The operating mode of this device.
145 void SetMode (RedQueue::Mode mode);
148 * Get the encapsulation mode of this device.
150 * \returns The encapsulation mode of this device.
152 RedQueue::Mode GetMode (void);
155 * Get the average queue size
157 * \returns The average queue size in bytes
159 uint64_t GetAverageQueueSize (void);
163 void SetParams (uint32_t minTh, uint32_t maxTh,
164 uint32_t wLog, uint32_t pLog, uint64_t scellLog );
165 void StartIdlePeriod ();
166 void EndIdlePeriod ();
173 int CheckThresh (uint64_t avg);
174 int Processing (uint64_t avg);
175 int MarkProbability (uint64_t avg);
176 int DropPacket (Ptr<Packet> p);
178 uint64_t AvgFromIdleTime ();
179 uint64_t AvgCalc (uint32_t backlog);
181 ///< Avg = Avg*(1-W) + backlog*W
182 uint64_t AvgFromNonIdleTime (uint32_t backlog);
184 ///< burst + 1 - qmin/avpkt < (1-(1-W)^burst)/W
185 ///< this low-pass filter is used to calculate the avg queue size
186 uint32_t evalEwma (uint32_t minTh, uint32_t burst, uint32_t avpkt);
188 ///< Plog = log (prob / (qMax - qMin))
189 uint32_t evalP (uint32_t minTh, uint32_t maxTh, double prob);
191 ///< -log(1-W) * t/TxTime
192 uint32_t evalIdleDamping (uint32_t wLog, uint32_t avpkt, uint32_t rate);
194 uint32_t Rmask (uint32_t pLog);
195 uint32_t RedRandom ();
197 virtual bool DoEnqueue (Ptr<Packet> p);
198 virtual Ptr<Packet> DoDequeue (void);
199 virtual Ptr<const Packet> DoPeek (void) const;
202 std::list<Ptr<Packet> > m_packets;
206 uint32_t m_bytesInQueue;
208 ///< users' configurable options
209 uint32_t m_maxPackets;
214 * in bytes, use with burst to determine the time constant
215 * for average queue size calculations, for ewma
218 uint32_t m_minTh; ///> Min avg length threshold (bytes), should be < maxTh/2
219 uint32_t m_maxTh; ///> Max avg length threshold (bytes), should be >= 2*minTh
220 uint32_t m_rate; ///> bandwidth in bps
221 uint32_t m_wLog; ///> log(W) bits
222 uint32_t m_pLog; ///> random number bits log (P_max/(maxTh - minTh))
224 uint32_t m_scellLog; ///> cell size for idle damping
226 uint32_t m_count; ///> number of packets since last random number generation
227 uint32_t m_randNum; ///> a random number 0 ...2^Plog
229 uint64_t m_qavg; ///> average q length
234 Time m_idleStart; ///> start of current idle period
235 Uint32tVector m_sTable;
240 #endif /* RED_QUEUE_H */