A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
red-queue-disc.h
Go to the documentation of this file.
1/*
2 * Copyright © 2011 Marcos Talau
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Author: Marcos Talau (talau@users.sourceforge.net)
7 *
8 * Thanks to: Duy Nguyen<duy@soe.ucsc.edu> by RED efforts in NS3
9 *
10 *
11 * This file incorporates work covered by the following copyright and
12 * permission notice:
13 *
14 * Copyright (c) 1990-1997 Regents of the University of California.
15 * All rights reserved.
16 *
17 * Redistribution and use in source and binary forms, with or without
18 * modification, are permitted provided that the following conditions
19 * are met:
20 * 1. Redistributions of source code must retain the above copyright
21 * notice, this list of conditions and the following disclaimer.
22 * 2. Redistributions in binary form must reproduce the above copyright
23 * notice, this list of conditions and the following disclaimer in the
24 * documentation and/or other materials provided with the distribution.
25 * 3. Neither the name of the University nor of the Laboratory may be used
26 * to endorse or promote products derived from this software without
27 * specific prior written permission.
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
30 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
31 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
32 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
33 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
34 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
35 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
36 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
37 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
38 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
39 * SUCH DAMAGE.
40 */
41
42/*
43 * PORT NOTE: This code was ported from ns-2 (queue/red.h). Almost all
44 * comments also been ported from NS-2.
45 * This implementation aims to be close to the results cited in [0]
46 * [0] S.Floyd, K.Fall http://icir.org/floyd/papers/redsims.ps
47 */
48
49#ifndef RED_QUEUE_DISC_H
50#define RED_QUEUE_DISC_H
51
52#include "queue-disc.h"
53
54#include "ns3/boolean.h"
55#include "ns3/data-rate.h"
56#include "ns3/nstime.h"
57#include "ns3/random-variable-stream.h"
58
59namespace ns3
60{
61
62class TraceContainer;
63
64/**
65 * \ingroup traffic-control
66 *
67 * \brief A RED packet queue disc
68 */
69class RedQueueDisc : public QueueDisc
70{
71 public:
72 /**
73 * \brief Get the type ID.
74 * \return the object TypeId
75 */
76 static TypeId GetTypeId();
77 /**
78 * \brief RedQueueDisc Constructor
79 *
80 * Create a RED queue disc
81 */
83
84 /**
85 * \brief Destructor
86 *
87 * Destructor
88 */
89 ~RedQueueDisc() override;
90
91 /**
92 * \brief Used in Feng's Adaptive RED
93 */
95 {
96 Above, //!< When m_qAvg > m_maxTh
97 Between, //!< When m_maxTh < m_qAvg < m_minTh
98 Below, //!< When m_qAvg < m_minTh
99 };
100
101 /**
102 * \brief Drop types
103 */
104 enum
105 {
106 DTYPE_NONE, //!< Ok, no drop
107 DTYPE_FORCED, //!< A "forced" drop
108 DTYPE_UNFORCED, //!< An "unforced" (random) drop
109 };
110
111 /**
112 * \brief Set the alpha value to adapt m_curMaxP.
113 *
114 * \param alpha The value of alpha to adapt m_curMaxP.
115 */
116 void SetAredAlpha(double alpha);
117
118 /**
119 * \brief Get the alpha value to adapt m_curMaxP.
120 *
121 * \returns The alpha value to adapt m_curMaxP.
122 */
123 double GetAredAlpha();
124
125 /**
126 * \brief Set the beta value to adapt m_curMaxP.
127 *
128 * \param beta The value of beta to adapt m_curMaxP.
129 */
130 void SetAredBeta(double beta);
131
132 /**
133 * \brief Get the beta value to adapt m_curMaxP.
134 *
135 * \returns The beta value to adapt m_curMaxP.
136 */
137 double GetAredBeta();
138
139 /**
140 * \brief Set the alpha value to adapt m_curMaxP in Feng's Adaptive RED.
141 *
142 * \param a The value of alpha to adapt m_curMaxP in Feng's Adaptive RED.
143 */
144 void SetFengAdaptiveA(double a);
145
146 /**
147 * \brief Get the alpha value to adapt m_curMaxP in Feng's Adaptive RED.
148 *
149 * \returns The alpha value to adapt m_curMaxP in Feng's Adaptive RED.
150 */
151 double GetFengAdaptiveA();
152
153 /**
154 * \brief Set the beta value to adapt m_curMaxP in Feng's Adaptive RED.
155 *
156 * \param b The value of beta to adapt m_curMaxP in Feng's Adaptive RED.
157 */
158 void SetFengAdaptiveB(double b);
159
160 /**
161 * \brief Get the beta value to adapt m_curMaxP in Feng's Adaptive RED.
162 *
163 * \returns The beta value to adapt m_curMaxP in Feng's Adaptive RED.
164 */
165 double GetFengAdaptiveB();
166
167 /**
168 * \brief Set the thresh limits of RED.
169 *
170 * \param minTh Minimum thresh in bytes or packets.
171 * \param maxTh Maximum thresh in bytes or packets.
172 */
173 void SetTh(double minTh, double maxTh);
174
175 /**
176 * Assign a fixed random variable stream number to the random variables
177 * used by this model. Return the number of streams (possibly zero) that
178 * have been assigned.
179 *
180 * \param stream first stream index to use
181 * \return the number of stream indices assigned by this model
182 */
183 int64_t AssignStreams(int64_t stream);
184
185 // Reasons for dropping packets
186 static constexpr const char* UNFORCED_DROP = "Unforced drop"; //!< Early probability drops
187 static constexpr const char* FORCED_DROP = "Forced drop"; //!< Forced drops, m_qAvg > m_maxTh
188 // Reasons for marking packets
189 static constexpr const char* UNFORCED_MARK = "Unforced mark"; //!< Early probability marks
190 static constexpr const char* FORCED_MARK = "Forced mark"; //!< Forced marks, m_qAvg > m_maxTh
191
192 protected:
193 /**
194 * \brief Dispose of the object
195 */
196 void DoDispose() override;
197
198 private:
199 bool DoEnqueue(Ptr<QueueDiscItem> item) override;
200 Ptr<QueueDiscItem> DoDequeue() override;
202 bool CheckConfig() override;
203
204 /**
205 * \brief Initialize the queue parameters.
206 *
207 * Note: if the link bandwidth changes in the course of the
208 * simulation, the bandwidth-dependent RED parameters do not change.
209 * This should be fixed, but it would require some extra parameters,
210 * and didn't seem worth the trouble...
211 */
212 void InitializeParams() override;
213 /**
214 * \brief Compute the average queue size
215 * \param nQueued number of queued packets
216 * \param m simulated number of packets arrival during idle period
217 * \param qAvg average queue size
218 * \param qW queue weight given to cur q size sample
219 * \returns new average queue size
220 */
221 double Estimator(uint32_t nQueued, uint32_t m, double qAvg, double qW);
222 /**
223 * \brief Update m_curMaxP
224 * \param newAve new average queue length
225 */
226 void UpdateMaxP(double newAve);
227 /**
228 * \brief Update m_curMaxP based on Feng's Adaptive RED
229 * \param newAve new average queue length
230 */
231 void UpdateMaxPFeng(double newAve);
232 /**
233 * \brief Check if a packet needs to be dropped due to probability mark
234 * \param item queue item
235 * \param qSize queue size
236 * \returns false for no drop/mark, true for drop
237 */
238 bool DropEarly(Ptr<QueueDiscItem> item, uint32_t qSize);
239 /**
240 * \brief Returns a probability using these function parameters for the DropEarly function
241 * \returns Prob. of packet drop before "count"
242 */
243 double CalculatePNew();
244 /**
245 * \brief Returns a probability using these function parameters for the DropEarly function
246 * \param p Prob. of packet drop before "count"
247 * \param size packet size
248 * \returns Prob. of packet drop
249 */
250 double ModifyP(double p, uint32_t size);
251
252 // ** Variables supplied by user
253 uint32_t m_meanPktSize; //!< Avg pkt size
254 uint32_t m_idlePktSize; //!< Avg pkt size used during idle times
255 bool m_isWait; //!< True for waiting between dropped packets
256 bool m_isGentle; //!< True to increase dropping prob. slowly when m_qAvg exceeds m_maxTh
257 bool m_isARED; //!< True to enable Adaptive RED
258 bool m_isAdaptMaxP; //!< True to adapt m_curMaxP
259 double m_minTh; //!< Minimum threshold for m_qAvg (bytes or packets)
260 double m_maxTh; //!< Maximum threshold for m_qAvg (bytes or packets), should be >= 2 * m_minTh
261 double m_qW; //!< Queue weight given to cur queue size sample
262 double m_lInterm; //!< The max probability of dropping a packet
263 Time m_targetDelay; //!< Target average queuing delay in ARED
264 Time m_interval; //!< Time interval to update m_curMaxP
265 double m_top; //!< Upper bound for m_curMaxP in ARED
266 double m_bottom; //!< Lower bound for m_curMaxP in ARED
267 double m_alpha; //!< Increment parameter for m_curMaxP in ARED
268 double m_beta; //!< Decrement parameter for m_curMaxP in ARED
269 Time m_rtt; //!< Rtt to be considered while automatically setting m_bottom in ARED
270 bool m_isFengAdaptive; //!< True to enable Feng's Adaptive RED
271 bool m_isNonlinear; //!< True to enable Nonlinear RED
272 double m_b; //!< Increment parameter for m_curMaxP in Feng's Adaptive RED
273 double m_a; //!< Decrement parameter for m_curMaxP in Feng's Adaptive RED
274 bool m_isNs1Compat; //!< Ns-1 compatibility
275 DataRate m_linkBandwidth; //!< Link bandwidth
276 Time m_linkDelay; //!< Link delay
277 bool m_useEcn; //!< True if ECN is used (packets are marked instead of being dropped)
278 bool m_useHardDrop; //!< True if packets are always dropped above max threshold
279
280 // ** Variables maintained by RED
281 double m_vA; //!< 1.0 / (m_maxTh - m_minTh)
282 double m_vB; //!< -m_minTh / (m_maxTh - m_minTh)
283 double m_vC; //!< (1.0 - m_curMaxP) / m_maxTh - used in "gentle" mode
284 double m_vD; //!< 2.0 * m_curMaxP - 1.0 - used in "gentle" mode
285 double m_curMaxP; //!< Current max_p
286 Time m_lastSet; //!< Last time m_curMaxP was updated
287 double m_vProb; //!< Prob. of packet drop
288 uint32_t m_countBytes; //!< Number of bytes since last drop
289 uint32_t m_old; //!< 0 when average queue first exceeds threshold
290 uint32_t m_idle; //!< 0/1 idle status
291 double m_ptc; //!< packet time constant in packets/second
292 double m_qAvg; //!< Average queue length
293 uint32_t m_count; //!< Number of packets since last random number generation
294 FengStatus m_fengStatus; //!< For use in Feng's Adaptive RED
295 /**
296 * 0 for default RED
297 * 1 experimental (see red-queue-disc.cc)
298 * 2 experimental (see red-queue-disc.cc)
299 * 3 use Idle packet size in the ptc
300 */
302 Time m_idleTime; //!< Start of current idle period
303
305};
306
307}; // namespace ns3
308
309#endif // RED_QUEUE_DISC_H
Class for representing data rates.
Definition data-rate.h:78
Smart pointer class similar to boost::intrusive_ptr.
QueueDisc is an abstract base class providing the interface and implementing the operations common to...
Definition queue-disc.h:173
A RED packet queue disc.
Time m_idleTime
Start of current idle period.
Time m_linkDelay
Link delay.
RedQueueDisc()
RedQueueDisc Constructor.
void UpdateMaxPFeng(double newAve)
Update m_curMaxP based on Feng's Adaptive RED.
DataRate m_linkBandwidth
Link bandwidth.
double m_vA
1.0 / (m_maxTh - m_minTh)
void SetFengAdaptiveB(double b)
Set the beta value to adapt m_curMaxP in Feng's Adaptive RED.
Time m_rtt
Rtt to be considered while automatically setting m_bottom in ARED.
static constexpr const char * FORCED_DROP
Forced drops, m_qAvg > m_maxTh.
FengStatus
Used in Feng's Adaptive RED.
@ Above
When m_qAvg > m_maxTh.
@ Between
When m_maxTh < m_qAvg < m_minTh.
@ Below
When m_qAvg < m_minTh.
static constexpr const char * UNFORCED_DROP
Early probability drops.
bool DoEnqueue(Ptr< QueueDiscItem > item) override
This function actually enqueues a packet into the queue disc.
double GetAredAlpha()
Get the alpha value to adapt m_curMaxP.
double ModifyP(double p, uint32_t size)
Returns a probability using these function parameters for the DropEarly function.
double m_a
Decrement parameter for m_curMaxP in Feng's Adaptive RED.
double GetFengAdaptiveB()
Get the beta value to adapt m_curMaxP in Feng's Adaptive RED.
void SetAredBeta(double beta)
Set the beta value to adapt m_curMaxP.
bool m_isAdaptMaxP
True to adapt m_curMaxP.
void SetTh(double minTh, double maxTh)
Set the thresh limits of RED.
uint32_t m_cautious
0 for default RED 1 experimental (see red-queue-disc.cc) 2 experimental (see red-queue-disc....
double m_alpha
Increment parameter for m_curMaxP in ARED.
bool m_isARED
True to enable Adaptive RED.
Time m_interval
Time interval to update m_curMaxP.
int64_t AssignStreams(int64_t stream)
Assign a fixed random variable stream number to the random variables used by this model.
bool CheckConfig() override
Check whether the current configuration is correct.
FengStatus m_fengStatus
For use in Feng's Adaptive RED.
bool m_useHardDrop
True if packets are always dropped above max threshold.
static constexpr const char * UNFORCED_MARK
Early probability marks.
double GetAredBeta()
Get the beta value to adapt m_curMaxP.
uint32_t m_old
0 when average queue first exceeds threshold
void SetFengAdaptiveA(double a)
Set the alpha value to adapt m_curMaxP in Feng's Adaptive RED.
Ptr< QueueDiscItem > DoDequeue() override
This function actually extracts a packet from the queue disc.
bool m_isWait
True for waiting between dropped packets.
bool m_useEcn
True if ECN is used (packets are marked instead of being dropped)
double m_maxTh
Maximum threshold for m_qAvg (bytes or packets), should be >= 2 * m_minTh.
static constexpr const char * FORCED_MARK
Forced marks, m_qAvg > m_maxTh.
bool m_isNonlinear
True to enable Nonlinear RED.
double m_minTh
Minimum threshold for m_qAvg (bytes or packets)
double m_top
Upper bound for m_curMaxP in ARED.
uint32_t m_meanPktSize
Avg pkt size.
double m_beta
Decrement parameter for m_curMaxP in ARED.
double m_lInterm
The max probability of dropping a packet.
uint32_t m_countBytes
Number of bytes since last drop.
void SetAredAlpha(double alpha)
Set the alpha value to adapt m_curMaxP.
bool m_isNs1Compat
Ns-1 compatibility.
double Estimator(uint32_t nQueued, uint32_t m, double qAvg, double qW)
Compute the average queue size.
double m_vB
-m_minTh / (m_maxTh - m_minTh)
double m_b
Increment parameter for m_curMaxP in Feng's Adaptive RED.
double m_bottom
Lower bound for m_curMaxP in ARED.
Time m_lastSet
Last time m_curMaxP was updated.
Time m_targetDelay
Target average queuing delay in ARED.
double m_ptc
packet time constant in packets/second
void InitializeParams() override
Initialize the queue parameters.
double CalculatePNew()
Returns a probability using these function parameters for the DropEarly function.
void UpdateMaxP(double newAve)
Update m_curMaxP.
bool m_isFengAdaptive
True to enable Feng's Adaptive RED.
static TypeId GetTypeId()
Get the type ID.
uint32_t m_count
Number of packets since last random number generation.
void DoDispose() override
Dispose of the object.
bool DropEarly(Ptr< QueueDiscItem > item, uint32_t qSize)
Check if a packet needs to be dropped due to probability mark.
Ptr< const QueueDiscItem > DoPeek() override
Return a copy of the next packet the queue disc will extract.
uint32_t m_idle
0/1 idle status
Ptr< UniformRandomVariable > m_uv
rng stream
double GetFengAdaptiveA()
Get the alpha value to adapt m_curMaxP in Feng's Adaptive RED.
~RedQueueDisc() override
Destructor.
double m_vD
2.0 * m_curMaxP - 1.0 - used in "gentle" mode
double m_qAvg
Average queue length.
@ DTYPE_UNFORCED
An "unforced" (random) drop.
@ DTYPE_FORCED
A "forced" drop.
@ DTYPE_NONE
Ok, no drop.
bool m_isGentle
True to increase dropping prob.
double m_vC
(1.0 - m_curMaxP) / m_maxTh - used in "gentle" mode
uint32_t m_idlePktSize
Avg pkt size used during idle times.
double m_qW
Queue weight given to cur queue size sample.
double m_curMaxP
Current max_p.
Simulation virtual time values and global simulation resolution.
Definition nstime.h:94
a unique identifier for an interface.
Definition type-id.h:48
Every class exported by the ns3 library is enclosed in the ns3 namespace.