A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
cobalt-queue-disc.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2019 NITK Surathkal
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Cobalt, the CoDel - BLUE - Alternate Queueing discipline
7 * Based on linux code.
8 *
9 * Ported to ns-3 by: Vignesh Kannan <vignesh2496@gmail.com>
10 * Harsh Lara <harshapplefan@gmail.com>
11 * Jendaipou Palmei <jendaipoupalmei@gmail.com>
12 * Shefali Gupta <shefaligups11@gmail.com>
13 * Mohit P. Tahiliani <tahiliani@nitk.edu.in>
14 *
15 */
16
17#ifndef COBALT_H
18#define COBALT_H
19
20#include "queue-disc.h"
21
22#include "ns3/boolean.h"
23#include "ns3/data-rate.h"
24#include "ns3/nstime.h"
25#include "ns3/random-variable-stream.h"
26#include "ns3/simulator.h"
27#include "ns3/string.h"
28#include "ns3/trace-source-accessor.h"
29#include "ns3/traced-value.h"
30
31namespace ns3
32{
33
34#define REC_INV_SQRT_CACHE (16)
35#define DEFAULT_COBALT_LIMIT 1000
36
37class TraceContainer;
38
39/**
40 * \ingroup traffic-control
41 *
42 * \brief Cobalt packet queue disc
43 *
44 * Cobalt uses CoDel and BLUE algorithms in parallel, in order
45 * to obtain the best features of each. CoDel is excellent on flows
46 * which respond to congestion signals in a TCP-like way. BLUE is far
47 * more effective on unresponsive flows.
48 */
50{
51 public:
52 /**
53 * \brief Get the type ID.
54 * \return the object TypeId
55 */
56 static TypeId GetTypeId();
57
58 /**
59 * \brief CobaltQueueDisc Constructor
60 *
61 * Create a Cobalt queue disc
62 */
64
65 /**
66 * \brief Destructor
67 *
68 * Destructor
69 */
70 ~CobaltQueueDisc() override;
71
72 /**
73 * \brief Get the target queue delay
74 *
75 * \returns The target queue delay
76 */
77 Time GetTarget() const;
78
79 /**
80 * \brief Get the interval
81 *
82 * \returns The interval
83 */
84 Time GetInterval() const;
85
86 /**
87 * \brief Get the time for next packet drop while in the dropping state
88 *
89 * \returns The time (in microseconds) for next packet drop
90 */
91 int64_t GetDropNext() const;
92
93 static constexpr const char* TARGET_EXCEEDED_DROP =
94 "Target exceeded drop"; //!< Sojourn time above target
95 static constexpr const char* OVERLIMIT_DROP = "Overlimit drop"; //!< Overlimit dropped packet
96 static constexpr const char* FORCED_MARK =
97 "forcedMark"; //!< forced marks by Codel on ECN-enabled
98 static constexpr const char* CE_THRESHOLD_EXCEEDED_MARK =
99 "CE threshold exceeded mark"; //!< Sojourn time above CE threshold
100
101 /**
102 * \brief Get the drop probability of Blue
103 *
104 * \returns The current value of Blue's drop probability
105 */
106 double GetPdrop() const;
107
108 /**
109 * Assign a fixed random variable stream number to the random variables
110 * used by this model. Return the number of streams (possibly zero) that
111 * have been assigned.
112 *
113 * \param stream first stream index to use
114 * \return the number of stream indices assigned by this model
115 */
116 int64_t AssignStreams(int64_t stream);
117
118 /**
119 * Return the unsigned 32-bit integer representation of the input Time
120 * object. Units are microseconds
121 * @param t the input Time Object
122 * @return the unsigned 32-bit integer representation
123 */
124 int64_t Time2CoDel(Time t) const;
125
126 protected:
127 /**
128 * \brief Dispose of the object
129 */
130 void DoDispose() override;
131
132 private:
133 bool DoEnqueue(Ptr<QueueDiscItem> item) override;
134 Ptr<QueueDiscItem> DoDequeue() override;
136 bool CheckConfig() override;
137
138 /**
139 * \brief Initialize the queue parameters.
140 */
141 void InitializeParams() override;
142
143 /**
144 * \brief Calculate the reciprocal square root of m_count by using Newton's method
145 * http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots
146 * m_recInvSqrt (new) = (m_recInvSqrt (old) / 2) * (3 - m_count * m_recInvSqrt^2)
147 */
148 void NewtonStep();
149
150 /**
151 * \brief Determine the time for next drop
152 * CoDel control law is t + m_interval/sqrt(m_count).
153 * Here, we use m_recInvSqrt calculated by Newton's method in NewtonStep() to avoid
154 * both sqrt() and divide operations
155 *
156 * \param t Current next drop time
157 * \returns The new next drop time:
158 */
159 int64_t ControlLaw(int64_t t);
160
161 /**
162 * \brief Updates the inverse square root
163 */
164 void InvSqrt();
165
166 /**
167 * There is a big difference in timing between the accurate values placed in
168 * the cache and the approximations given by a single Newton step for small
169 * count values, particularly when stepping from count 1 to 2 or vice versa.
170 * Above 16, a single Newton step gives sufficient accuracy in either
171 * direction, given the precision stored.
172 *
173 * The magnitude of the error when stepping up to count 2 is such as to give
174 * the value that *should* have been produced at count 4.
175 */
176 void CacheInit();
177
178 /**
179 * Check if CoDel time a is successive to b
180 * @param a left operand
181 * @param b right operand
182 * @return true if a is greater than b
183 */
184
185 bool CoDelTimeAfter(int64_t a, int64_t b);
186
187 /**
188 * Check if CoDel time a is successive or equal to b
189 * @param a left operand
190 * @param b right operand
191 * @return true if a is greater than or equal to b
192 */
193 bool CoDelTimeAfterEq(int64_t a, int64_t b);
194
195 /**
196 * Called when the queue becomes full to alter the drop probabilities of Blue
197 * \param now time in CoDel time units (microseconds)
198 */
199 void CobaltQueueFull(int64_t now);
200
201 /**
202 * Called when the queue becomes empty to alter the drop probabilities of Blue
203 * \param now time in CoDel time units (microseconds)
204 */
205 void CobaltQueueEmpty(int64_t now);
206
207 /**
208 * Called to decide whether the current packet should be dropped based on decisions taken by
209 * Blue and Codel working parallelly
210 *
211 * \return true if the packet should be dropped, false otherwise
212 * \param item current packet
213 * \param now time in CoDel time units (microseconds)
214 */
215 bool CobaltShouldDrop(Ptr<QueueDiscItem> item, int64_t now);
216
217 // Common to CoDel and Blue
218 // Maintained by Cobalt
219 Stats m_stats; //!< Cobalt statistics
220
221 // Codel parameters
222 // Maintained by Cobalt
223 TracedValue<uint32_t> m_count; //!< Number of packets dropped since entering drop state
224 TracedValue<int64_t> m_dropNext; //!< Time to drop next packet
225 TracedValue<bool> m_dropping; //!< True if in dropping state
226 uint32_t m_recInvSqrt; //!< Reciprocal inverse square root
228 0}; //!< Cache to maintain some initial values of InvSqrt
229
230 // Supplied by user
231 Time m_interval; //!< sliding minimum time window width
232 Time m_target; //!< target queue delay
233 bool m_useEcn; //!< True if ECN is used (packets are marked instead of being dropped)
234 Time m_ceThreshold; //!< Threshold above which to CE mark
235 bool m_useL4s; //!< True if L4S is used (ECT1 packets are marked at CE threshold)
236 Time m_blueThreshold; //!< Threshold to enable blue enhancement
237
238 // Blue parameters
239 // Maintained by Cobalt
241 uint32_t m_lastUpdateTimeBlue; //!< Blue's last update time for drop probability
242
243 // Supplied by user
244 double m_increment; //!< increment value for marking probability
245 double m_decrement; //!< decrement value for marking probability
246 double m_pDrop; //!< Drop Probability
247};
248
249} // namespace ns3
250
251#endif /* COBALT_H */
Cobalt packet queue disc.
Time m_ceThreshold
Threshold above which to CE mark.
uint32_t m_recInvSqrtCache[REC_INV_SQRT_CACHE]
Cache to maintain some initial values of InvSqrt.
Time m_target
target queue delay
static constexpr const char * CE_THRESHOLD_EXCEEDED_MARK
Sojourn time above CE threshold.
bool CheckConfig() override
Check whether the current configuration is correct.
void NewtonStep()
Calculate the reciprocal square root of m_count by using Newton's method http://en....
Time GetTarget() const
Get the target queue delay.
int64_t GetDropNext() const
Get the time for next packet drop while in the dropping state.
void InitializeParams() override
Initialize the queue parameters.
bool CoDelTimeAfterEq(int64_t a, int64_t b)
Check if CoDel time a is successive or equal to b.
void InvSqrt()
Updates the inverse square root.
double GetPdrop() const
Get the drop probability of Blue.
int64_t AssignStreams(int64_t stream)
Assign a fixed random variable stream number to the random variables used by this model.
void DoDispose() override
Dispose of the object.
TracedValue< uint32_t > m_count
Number of packets dropped since entering drop state.
Stats m_stats
Cobalt statistics.
double m_increment
increment value for marking probability
void CobaltQueueFull(int64_t now)
Called when the queue becomes full to alter the drop probabilities of Blue.
Time m_interval
sliding minimum time window width
double m_decrement
decrement value for marking probability
bool CobaltShouldDrop(Ptr< QueueDiscItem > item, int64_t now)
Called to decide whether the current packet should be dropped based on decisions taken by Blue and Co...
static TypeId GetTypeId()
Get the type ID.
Ptr< QueueDiscItem > DoDequeue() override
This function actually extracts a packet from the queue disc.
void CacheInit()
There is a big difference in timing between the accurate values placed in the cache and the approxima...
~CobaltQueueDisc() override
Destructor.
static constexpr const char * TARGET_EXCEEDED_DROP
Sojourn time above target.
int64_t Time2CoDel(Time t) const
Return the unsigned 32-bit integer representation of the input Time object.
bool CoDelTimeAfter(int64_t a, int64_t b)
Check if CoDel time a is successive to b.
Time GetInterval() const
Get the interval.
double m_pDrop
Drop Probability.
CobaltQueueDisc()
CobaltQueueDisc Constructor.
int64_t ControlLaw(int64_t t)
Determine the time for next drop CoDel control law is t + m_interval/sqrt(m_count).
static constexpr const char * FORCED_MARK
forced marks by Codel on ECN-enabled
Time m_blueThreshold
Threshold to enable blue enhancement.
uint32_t m_recInvSqrt
Reciprocal inverse square root.
Ptr< UniformRandomVariable > m_uv
Rng stream.
uint32_t m_lastUpdateTimeBlue
Blue's last update time for drop probability.
static constexpr const char * OVERLIMIT_DROP
Overlimit dropped packet.
TracedValue< bool > m_dropping
True if in dropping state.
Ptr< const QueueDiscItem > DoPeek() override
Return a copy of the next packet the queue disc will extract.
bool m_useEcn
True if ECN is used (packets are marked instead of being dropped)
bool DoEnqueue(Ptr< QueueDiscItem > item) override
This function actually enqueues a packet into the queue disc.
TracedValue< int64_t > m_dropNext
Time to drop next packet.
void CobaltQueueEmpty(int64_t now)
Called when the queue becomes empty to alter the drop probabilities of Blue.
bool m_useL4s
True if L4S is used (ECT1 packets are marked at CE threshold)
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
Simulation virtual time values and global simulation resolution.
Definition nstime.h:94
Trace classes with value semantics.
a unique identifier for an interface.
Definition type-id.h:48
#define REC_INV_SQRT_CACHE
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Structure that keeps the queue disc statistics.
Definition queue-disc.h:177