A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
codel-queue-disc.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2012 Andrew McGregor
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Codel, the COntrolled DELay Queueing discipline
7 * Based on ns2 simulation code presented by Kathie Nichols
8 *
9 * This port based on linux kernel code by
10 * Authors:
11 * Dave Täht <d@taht.net>
12 * Eric Dumazet <edumazet@google.com>
13 *
14 * Ported to ns-3 by: Andrew McGregor <andrewmcgr@gmail.com>
15 */
16
17#include "codel-queue-disc.h"
18
19#include "ns3/abort.h"
20#include "ns3/drop-tail-queue.h"
21#include "ns3/enum.h"
22#include "ns3/log.h"
23#include "ns3/object-factory.h"
24#include "ns3/uinteger.h"
25
26namespace ns3
27{
28
29NS_LOG_COMPONENT_DEFINE("CoDelQueueDisc");
30
31/**
32 * Performs a reciprocal divide, similar to the
33 * Linux kernel reciprocal_divide function
34 * \param A numerator
35 * \param R reciprocal of the denominator B
36 * \return the value of A/B
37 */
38/* borrowed from the linux kernel */
39static inline uint32_t
41{
42 return (uint32_t)(((uint64_t)A * R) >> 32);
43}
44
45/* end kernel borrowings */
46
47/**
48 * Returns the current time translated in CoDel time representation
49 * \return the current time
50 */
51static uint32_t
53{
54 Time time = Simulator::Now();
55 uint64_t ns = time.GetNanoSeconds();
56
57 return static_cast<uint32_t>(ns >> CODEL_SHIFT);
58}
59
60NS_OBJECT_ENSURE_REGISTERED(CoDelQueueDisc);
61
62TypeId
64{
65 static TypeId tid =
66 TypeId("ns3::CoDelQueueDisc")
68 .SetGroupName("TrafficControl")
69 .AddConstructor<CoDelQueueDisc>()
70 .AddAttribute("UseEcn",
71 "True to use ECN (packets are marked instead of being dropped)",
72 BooleanValue(false),
75 .AddAttribute("UseL4s",
76 "True to use L4S (only ECT1 packets are marked at CE threshold)",
77 BooleanValue(false),
80 .AddAttribute(
81 "MaxSize",
82 "The maximum number of packets/bytes accepted by this queue disc.",
86 .AddAttribute("MinBytes",
87 "The CoDel algorithm minbytes parameter.",
88 UintegerValue(1500),
91 .AddAttribute("Interval",
92 "The CoDel algorithm interval",
93 StringValue("100ms"),
96 .AddAttribute("Target",
97 "The CoDel algorithm target queue delay",
98 StringValue("5ms"),
101 .AddAttribute("CeThreshold",
102 "The CoDel CE threshold for marking packets",
106 .AddTraceSource("Count",
107 "CoDel count",
109 "ns3::TracedValueCallback::Uint32")
110 .AddTraceSource("LastCount",
111 "CoDel lastcount",
113 "ns3::TracedValueCallback::Uint32")
114 .AddTraceSource("DropState",
115 "Dropping state",
117 "ns3::TracedValueCallback::Bool")
118 .AddTraceSource("DropNext",
119 "Time until next packet drop",
121 "ns3::TracedValueCallback::Uint32");
122
123 return tid;
124}
125
128 m_count(0),
129 m_lastCount(0),
130 m_dropping(false),
131 m_recInvSqrt(~0U >> REC_INV_SQRT_SHIFT),
132 m_firstAboveTime(0),
133 m_dropNext(0)
134{
135 NS_LOG_FUNCTION(this);
136}
137
142
143uint16_t
144CoDelQueueDisc::NewtonStep(uint16_t recInvSqrt, uint32_t count)
145{
147 uint32_t invsqrt = ((uint32_t)recInvSqrt) << REC_INV_SQRT_SHIFT;
148 uint32_t invsqrt2 = ((uint64_t)invsqrt * invsqrt) >> 32;
149 uint64_t val = (3LL << 32) - ((uint64_t)count * invsqrt2);
150
151 val >>= 2; /* avoid overflow */
152 val = (val * invsqrt) >> (32 - 2 + 1);
153 return static_cast<uint16_t>(val >> REC_INV_SQRT_SHIFT);
154}
155
158{
160 return t + ReciprocalDivide(interval, recInvSqrt << REC_INV_SQRT_SHIFT);
161}
162
163bool
165{
166 NS_LOG_FUNCTION(this << item);
167
168 if (GetCurrentSize() + item > GetMaxSize())
169 {
170 NS_LOG_LOGIC("Queue full -- dropping pkt");
172 return false;
173 }
174
175 bool retval = GetInternalQueue(0)->Enqueue(item);
176
177 // If Queue::Enqueue fails, QueueDisc::DropBeforeEnqueue is called by the
178 // internal queue because QueueDisc::AddInternalQueue sets the trace callback
179
180 NS_LOG_LOGIC("Number packets " << GetInternalQueue(0)->GetNPackets());
181 NS_LOG_LOGIC("Number bytes " << GetInternalQueue(0)->GetNBytes());
182
183 return retval;
184}
185
186bool
188{
189 NS_LOG_FUNCTION(this);
190 bool okToDrop;
191
192 if (!item)
193 {
195 return false;
196 }
197
198 Time delta = Simulator::Now() - item->GetTimeStamp();
199 NS_LOG_INFO("Sojourn time " << delta.As(Time::MS));
200 uint32_t sojournTime = Time2CoDel(delta);
201
202 if (CoDelTimeBefore(sojournTime, Time2CoDel(m_target)) ||
204 {
205 // went below so we'll stay below for at least q->interval
206 NS_LOG_LOGIC("Sojourn time is below target or number of bytes in queue is less than "
207 "minBytes; packet should not be dropped");
209 return false;
210 }
211 okToDrop = false;
212 if (m_firstAboveTime == 0)
213 {
214 /* just went above from below. If we stay above
215 * for at least q->interval we'll say it's ok to drop
216 */
217 NS_LOG_LOGIC("Sojourn time has just gone above target from below, need to stay above for "
218 "at least q->interval before packet can be dropped. ");
220 }
221 else if (CoDelTimeAfter(now, m_firstAboveTime))
222 {
223 NS_LOG_LOGIC("Sojourn time has been above target for at least q->interval; it's OK to "
224 "(possibly) drop packet.");
225 okToDrop = true;
226 }
227 return okToDrop;
228}
229
232{
233 NS_LOG_FUNCTION(this);
234
235 Ptr<QueueDiscItem> item = GetInternalQueue(0)->Dequeue();
236 if (!item)
237 {
238 // Leave dropping state when queue is empty
239 m_dropping = false;
240 NS_LOG_LOGIC("Queue empty");
241 return nullptr;
242 }
243 uint32_t ldelay = Time2CoDel(Simulator::Now() - item->GetTimeStamp());
244 if (item && m_useL4s)
245 {
246 uint8_t tosByte = 0;
247 if (item->GetUint8Value(QueueItem::IP_DSFIELD, tosByte) &&
248 (((tosByte & 0x3) == 1) || (tosByte & 0x3) == 3))
249 {
250 if ((tosByte & 0x3) == 1)
251 {
252 NS_LOG_DEBUG("ECT1 packet " << static_cast<uint16_t>(tosByte & 0x3));
253 }
254 else
255 {
256 NS_LOG_DEBUG("CE packet " << static_cast<uint16_t>(tosByte & 0x3));
257 }
258
261 {
262 NS_LOG_LOGIC("Marking due to CeThreshold " << m_ceThreshold.GetSeconds());
263 }
264 return item;
265 }
266 }
267
268 uint32_t now = CoDelGetTime();
269
270 NS_LOG_LOGIC("Popped " << item);
271 NS_LOG_LOGIC("Number packets remaining " << GetInternalQueue(0)->GetNPackets());
272 NS_LOG_LOGIC("Number bytes remaining " << GetInternalQueue(0)->GetNBytes());
273
274 // Determine if item should be dropped
275 bool okToDrop = OkToDrop(item, now);
276 bool isMarked = false;
277
278 if (m_dropping)
279 { // In the dropping state (sojourn time has gone above target and hasn't come down yet)
280 // Check if we can leave the dropping state or next drop should occur
281 NS_LOG_LOGIC("In dropping state, check if it's OK to leave or next drop should occur");
282 if (!okToDrop)
283 {
284 /* sojourn time fell below target - leave dropping state */
285 NS_LOG_LOGIC("Sojourn time goes below target, it's OK to leave dropping state.");
286 m_dropping = false;
287 }
288 else if (CoDelTimeAfterEq(now, m_dropNext))
289 {
290 while (m_dropping && CoDelTimeAfterEq(now, m_dropNext))
291 {
292 ++m_count;
294 // It's time for the next drop. Drop the current packet and
295 // dequeue the next. The dequeue might take us out of dropping
296 // state. If not, schedule the next drop.
297 // A large amount of packets in queue might result in drop
298 // rates so high that the next drop should happen now,
299 // hence the while loop.
300 if (m_useEcn && Mark(item, TARGET_EXCEEDED_MARK))
301 {
302 isMarked = true;
303 NS_LOG_LOGIC("Sojourn time is still above target and it's time for next drop "
304 "or mark; marking "
305 << item);
306 NS_LOG_LOGIC("Running ControlLaw for input m_dropNext: " << (double)m_dropNext /
307 1000000);
309 NS_LOG_LOGIC("Scheduled next drop at " << (double)m_dropNext / 1000000);
310 goto end;
311 }
313 "Sojourn time is still above target and it's time for next drop; dropping "
314 << item);
316
317 item = GetInternalQueue(0)->Dequeue();
318
319 if (item)
320 {
321 NS_LOG_LOGIC("Popped " << item);
322 NS_LOG_LOGIC("Number packets remaining " << GetInternalQueue(0)->GetNPackets());
323 NS_LOG_LOGIC("Number bytes remaining " << GetInternalQueue(0)->GetNBytes());
324 }
325
326 if (!OkToDrop(item, now))
327 {
328 /* leave dropping state */
329 NS_LOG_LOGIC("Leaving dropping state");
330 m_dropping = false;
331 }
332 else
333 {
334 /* schedule the next drop */
335 NS_LOG_LOGIC("Running ControlLaw for input m_dropNext: " << (double)m_dropNext /
336 1000000);
338 NS_LOG_LOGIC("Scheduled next drop at " << (double)m_dropNext / 1000000);
339 }
340 }
341 }
342 }
343 else
344 {
345 // Not in the dropping state
346 // Decide if we have to enter the dropping state and drop the first packet
347 NS_LOG_LOGIC("Not in dropping state; decide if we have to enter the state and drop the "
348 "first packet");
349 if (okToDrop)
350 {
351 if (m_useEcn && Mark(item, TARGET_EXCEEDED_MARK))
352 {
353 isMarked = true;
354 NS_LOG_LOGIC("Sojourn time goes above target, marking the first packet "
355 << item << " and entering the dropping state");
356 }
357 else
358 {
359 // Drop the first packet and enter dropping state unless the queue is empty
360 NS_LOG_LOGIC("Sojourn time goes above target, dropping the first packet "
361 << item << " and entering the dropping state");
363 item = GetInternalQueue(0)->Dequeue();
364 if (item)
365 {
366 NS_LOG_LOGIC("Popped " << item);
367 NS_LOG_LOGIC("Number packets remaining " << GetInternalQueue(0)->GetNPackets());
368 NS_LOG_LOGIC("Number bytes remaining " << GetInternalQueue(0)->GetNBytes());
369 }
370 OkToDrop(item, now);
371 }
372 m_dropping = true;
373 /*
374 * if min went above target close to when we last went below it
375 * assume that the drop rate that controlled the queue on the
376 * last cycle is a good starting point to control it now.
377 */
378 int delta = m_count - m_lastCount;
379 if (delta > 1 && CoDelTimeBefore(now - m_dropNext, 16 * Time2CoDel(m_interval)))
380 {
381 m_count = delta;
383 }
384 else
385 {
386 m_count = 1;
388 }
390 NS_LOG_LOGIC("Running ControlLaw for input now: " << (double)now);
392 NS_LOG_LOGIC("Scheduled next drop at " << (double)m_dropNext / 1000000 << " now "
393 << (double)now / 1000000);
394 }
395 }
396end:
397 ldelay = Time2CoDel(Simulator::Now() - item->GetTimeStamp());
398 // In Linux, this branch of code is executed even if the packet has been marked
399 // according to the target delay above. If the ns-3 code were to do the same here,
400 // it would result in two counts of mark in the queue statistics. Therefore, we
401 // use the isMarked flag to suppress a second attempt at marking.
402 if (!isMarked && item && !m_useL4s && m_useEcn &&
404 {
405 NS_LOG_LOGIC("Marking due to CeThreshold " << m_ceThreshold.GetSeconds());
406 }
407 return item;
408}
409
410Time
412{
413 return m_target;
414}
415
416Time
421
427
428bool
430{
431 return ((int64_t)(a) - (int64_t)(b) > 0);
432}
433
434bool
436{
437 return ((int64_t)(a) - (int64_t)(b) >= 0);
438}
439
440bool
442{
443 return ((int64_t)(a) - (int64_t)(b) < 0);
444}
445
446bool
448{
449 return ((int64_t)(a) - (int64_t)(b) <= 0);
450}
451
454{
455 return static_cast<uint32_t>(t.GetNanoSeconds() >> CODEL_SHIFT);
456}
457
458bool
460{
461 NS_LOG_FUNCTION(this);
462 if (GetNQueueDiscClasses() > 0)
463 {
464 NS_LOG_ERROR("CoDelQueueDisc cannot have classes");
465 return false;
466 }
467
468 if (GetNPacketFilters() > 0)
469 {
470 NS_LOG_ERROR("CoDelQueueDisc cannot have packet filters");
471 return false;
472 }
473
474 if (GetNInternalQueues() == 0)
475 {
476 // add a DropTail queue
480 }
481
482 if (GetNInternalQueues() != 1)
483 {
484 NS_LOG_ERROR("CoDelQueueDisc needs 1 internal queue");
485 return false;
486 }
487
488 return true;
489}
490
491void
496
497} // namespace ns3
A CoDel packet queue disc.
bool CheckConfig() override
Check whether the current configuration is correct.
uint32_t GetDropNext()
Get the time for next packet drop while in the dropping state.
static uint16_t NewtonStep(uint16_t recInvSqrt, uint32_t count)
Calculate the reciprocal square root of m_count by using Newton's method http://en....
static constexpr const char * OVERLIMIT_DROP
Overlimit dropped packet.
static uint32_t ControlLaw(uint32_t t, uint32_t interval, uint32_t recInvSqrt)
Determine the time for next drop CoDel control law is t + m_interval/sqrt(m_count).
static constexpr const char * TARGET_EXCEEDED_DROP
Sojourn time above target.
uint16_t m_recInvSqrt
Reciprocal inverse square root.
bool CoDelTimeBeforeEq(uint32_t a, uint32_t b)
Check if CoDel time a is preceding or equal to b.
void InitializeParams() override
Initialize parameters (if any) before the first packet is enqueued.
Time m_ceThreshold
Threshold above which to CE mark.
Time GetInterval()
Get the interval.
Ptr< QueueDiscItem > DoDequeue() override
Remove a packet from queue based on the current state If we are in dropping state,...
uint32_t m_minBytes
Minimum bytes in queue to allow a packet drop.
bool CoDelTimeAfterEq(uint32_t a, uint32_t b)
Check if CoDel time a is successive or equal to b.
static constexpr const char * CE_THRESHOLD_EXCEEDED_MARK
Sojourn time above CE threshold.
TracedValue< uint32_t > m_count
Number of packets dropped since entering drop state.
bool m_useL4s
True if L4S is used (ECT1 packets are marked at CE threshold)
bool OkToDrop(Ptr< QueueDiscItem > item, uint32_t now)
Determine whether a packet is OK to be dropped.
TracedValue< uint32_t > m_lastCount
Last number of packets dropped since entering drop state.
Time m_target
5 ms target queue delay
uint32_t Time2CoDel(Time t)
Return the unsigned 32-bit integer representation of the input Time object.
CoDelQueueDisc()
CoDelQueueDisc Constructor.
uint32_t m_firstAboveTime
Time to declare sojourn time above target.
Time GetTarget()
Get the target queue delay.
bool m_useEcn
True if ECN is used (packets are marked instead of being dropped)
TracedValue< bool > m_dropping
True if in dropping state.
bool CoDelTimeAfter(uint32_t a, uint32_t b)
Check if CoDel time a is successive to b.
bool CoDelTimeBefore(uint32_t a, uint32_t b)
Check if CoDel time a is preceding b.
bool DoEnqueue(Ptr< QueueDiscItem > item) override
Add a packet to the queue.
static constexpr const char * TARGET_EXCEEDED_MARK
Sojourn time above target.
Time m_interval
100 ms sliding minimum time window width
TracedValue< uint32_t > m_dropNext
Time to drop next packet.
static TypeId GetTypeId()
Get the type ID.
A FIFO packet queue that drops tail-end packets on overflow.
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
void AddInternalQueue(Ptr< InternalQueue > queue)
Add an internal queue to the tail of the list of queues.
uint32_t GetNPackets() const
Get the number of packets stored by the queue disc.
uint32_t GetNBytes() const
Get the amount of bytes stored by the queue disc.
Ptr< InternalQueue > GetInternalQueue(std::size_t i) const
Get the i-th internal queue.
QueueSize GetCurrentSize() const
Get the current size of the queue disc in bytes, if operating in bytes mode, or packets,...
void DropAfterDequeue(Ptr< const QueueDiscItem > item, const char *reason)
Perform the actions required when the queue disc is notified of a packet dropped after dequeue.
std::size_t GetNQueueDiscClasses() const
Get the number of queue disc classes.
QueueSize GetMaxSize() const
Get the maximum size of the queue disc.
std::size_t GetNPacketFilters() const
Get the number of packet filters.
bool SetMaxSize(QueueSize size)
Set the maximum size of the queue disc.
std::size_t GetNInternalQueues() const
Get the number of internal queues.
bool Mark(Ptr< QueueDiscItem > item, const char *reason)
Marks the given packet and, if successful, updates the counters associated with the given reason.
void DropBeforeEnqueue(Ptr< const QueueDiscItem > item, const char *reason)
Perform the actions required when the queue disc is notified of a packet dropped before enqueue.
Class for representing queue sizes.
Definition queue-size.h:85
static Time Now()
Return the current simulation virtual time.
Definition simulator.cc:197
Hold variables of type string.
Definition string.h:45
Simulation virtual time values and global simulation resolution.
Definition nstime.h:94
int64_t GetNanoSeconds() const
Get an approximation of the time stored in this instance in the indicated unit.
Definition nstime.h:407
double GetSeconds() const
Get an approximation of the time stored in this instance in the indicated unit.
Definition nstime.h:392
@ MS
millisecond
Definition nstime.h:106
static Time Max()
Maximum representable Time Not to be confused with Max(Time,Time).
Definition nstime.h:286
a unique identifier for an interface.
Definition type-id.h:48
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition type-id.cc:1001
Hold an unsigned integer type.
Definition uinteger.h:34
#define DEFAULT_CODEL_LIMIT
#define REC_INV_SQRT_SHIFT
#define NS_LOG_ERROR(msg)
Use NS_LOG to output a message of level LOG_ERROR.
Definition log.h:243
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition log.h:191
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition log.h:257
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition log.h:271
#define NS_LOG_FUNCTION_NOARGS()
Output the name of the function.
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
#define NS_LOG_INFO(msg)
Use NS_LOG to output a message of level LOG_INFO.
Definition log.h:264
Ptr< T > CreateObjectWithAttributes(Args... args)
Allocate an Object on the heap and initialize with a set of attributes.
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition object-base.h:35
@ BYTES
Use number of bytes for queue size.
Definition queue-size.h:35
Ptr< const TraceSourceAccessor > MakeTraceSourceAccessor(T a)
Create a TraceSourceAccessor which will control access to the underlying trace source.
QueueDiscSizePolicy
Enumeration of the available policies to handle the queue disc size.
Definition queue-disc.h:96
@ SINGLE_INTERNAL_QUEUE
Used by queue discs with single internal queue.
Definition queue-disc.h:97
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Ptr< const AttributeAccessor > MakeQueueSizeAccessor(T1 a1)
Definition queue-size.h:210
Ptr< const AttributeChecker > MakeBooleanChecker()
Definition boolean.cc:113
Ptr< const AttributeChecker > MakeUintegerChecker()
Definition uinteger.h:85
Ptr< const AttributeAccessor > MakeTimeAccessor(T1 a1)
Definition nstime.h:1396
Ptr< const AttributeAccessor > MakeUintegerAccessor(T1 a1)
Definition uinteger.h:35
static int64_t CoDelGetTime()
Returns the current time translated in CoDel time representation.
static const int CODEL_SHIFT
Number of bits discarded from the time representation.
Ptr< const AttributeChecker > MakeQueueSizeChecker()
Definition queue-size.cc:18
static uint32_t ReciprocalDivide(uint32_t A, uint32_t R)
Performs a reciprocal divide, similar to the Linux kernel reciprocal_divide function.
Ptr< const AttributeAccessor > MakeBooleanAccessor(T1 a1)
Definition boolean.h:70
Ptr< const AttributeChecker > MakeTimeChecker()
Helper to make an unbounded Time checker.
Definition nstime.h:1416