A Discrete-Event Network Simulator
API
codel-queue-disc.cc
Go to the documentation of this file.
1/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/*
3 * Copyright (c) 2012 Andrew McGregor
4 *
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;
8 *
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.
13 *
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
17 *
18 * Codel, the COntrolled DELay Queueing discipline
19 * Based on ns2 simulation code presented by Kathie Nichols
20 *
21 * This port based on linux kernel code by
22 * Authors: Dave Täht <d@taht.net>
23 * Eric Dumazet <edumazet@google.com>
24 *
25 * Ported to ns-3 by: Andrew McGregor <andrewmcgr@gmail.com>
26*/
27
28#include "ns3/log.h"
29#include "ns3/enum.h"
30#include "ns3/uinteger.h"
31#include "ns3/abort.h"
32#include "codel-queue-disc.h"
33#include "ns3/object-factory.h"
34#include "ns3/drop-tail-queue.h"
35
36namespace ns3 {
37
38NS_LOG_COMPONENT_DEFINE ("CoDelQueueDisc");
39
47/* borrowed from the linux kernel */
49{
50 return (uint32_t)(((uint64_t)A * R) >> 32);
51}
52
53/* end kernel borrowings */
54
60{
61 Time time = Simulator::Now ();
62 uint64_t ns = time.GetNanoSeconds ();
63
64 return static_cast<uint32_t>(ns >> CODEL_SHIFT);
65}
66
67
68NS_OBJECT_ENSURE_REGISTERED (CoDelQueueDisc);
69
71{
72 static TypeId tid = TypeId ("ns3::CoDelQueueDisc")
74 .SetGroupName ("TrafficControl")
75 .AddConstructor<CoDelQueueDisc> ()
76 .AddAttribute ("UseEcn",
77 "True to use ECN (packets are marked instead of being dropped)",
78 BooleanValue (false),
81 .AddAttribute ("UseL4s",
82 "True to use L4S (only ECT1 packets are marked at CE threshold)",
83 BooleanValue (false),
86 .AddAttribute ("MaxSize",
87 "The maximum number of packets/bytes accepted by this queue disc.",
89 MakeQueueSizeAccessor (&QueueDisc::SetMaxSize,
91 MakeQueueSizeChecker ())
92 .AddAttribute ("MinBytes",
93 "The CoDel algorithm minbytes parameter.",
94 UintegerValue (1500),
96 MakeUintegerChecker<uint32_t> ())
97 .AddAttribute ("Interval",
98 "The CoDel algorithm interval",
99 StringValue ("100ms"),
102 .AddAttribute ("Target",
103 "The CoDel algorithm target queue delay",
104 StringValue ("5ms"),
107 .AddAttribute ("CeThreshold",
108 "The CoDel CE threshold for marking packets",
109 TimeValue (Time::Max ()),
112 .AddTraceSource ("Count",
113 "CoDel count",
115 "ns3::TracedValueCallback::Uint32")
116 .AddTraceSource ("LastCount",
117 "CoDel lastcount",
119 "ns3::TracedValueCallback::Uint32")
120 .AddTraceSource ("DropState",
121 "Dropping state",
123 "ns3::TracedValueCallback::Bool")
124 .AddTraceSource ("DropNext",
125 "Time until next packet drop",
127 "ns3::TracedValueCallback::Uint32")
128 ;
129
130 return tid;
131}
132
135 m_count (0),
136 m_lastCount (0),
137 m_dropping (false),
138 m_recInvSqrt (~0U >> REC_INV_SQRT_SHIFT),
139 m_firstAboveTime (0),
140 m_dropNext (0)
141{
142 NS_LOG_FUNCTION (this);
143}
144
146{
147 NS_LOG_FUNCTION (this);
148}
149
150uint16_t
151CoDelQueueDisc::NewtonStep (uint16_t recInvSqrt, uint32_t count)
152{
154 uint32_t invsqrt = ((uint32_t) recInvSqrt) << REC_INV_SQRT_SHIFT;
155 uint32_t invsqrt2 = ((uint64_t) invsqrt * invsqrt) >> 32;
156 uint64_t val = (3ll << 32) - ((uint64_t) count * invsqrt2);
157
158 val >>= 2; /* avoid overflow */
159 val = (val * invsqrt) >> (32 - 2 + 1);
160 return static_cast<uint16_t>(val >> REC_INV_SQRT_SHIFT);
161}
162
165{
167 return t + ReciprocalDivide (interval, recInvSqrt << REC_INV_SQRT_SHIFT);
168}
169
170bool
172{
173 NS_LOG_FUNCTION (this << item);
174
175 if (GetCurrentSize () + item > GetMaxSize ())
176 {
177 NS_LOG_LOGIC ("Queue full -- dropping pkt");
179 return false;
180 }
181
182 bool retval = GetInternalQueue (0)->Enqueue (item);
183
184 // If Queue::Enqueue fails, QueueDisc::DropBeforeEnqueue is called by the
185 // internal queue because QueueDisc::AddInternalQueue sets the trace callback
186
187 NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
188 NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
189
190 return retval;
191}
192
193bool
195{
196 NS_LOG_FUNCTION (this);
197 bool okToDrop;
198
199 if (!item)
200 {
202 return false;
203 }
204
205 Time delta = Simulator::Now () - item->GetTimeStamp ();
206 NS_LOG_INFO ("Sojourn time " << delta.As (Time::MS));
207 uint32_t sojournTime = Time2CoDel (delta);
208
209 if (CoDelTimeBefore (sojournTime, Time2CoDel (m_target))
211 {
212 // went below so we'll stay below for at least q->interval
213 NS_LOG_LOGIC ("Sojourn time is below target or number of bytes in queue is less than minBytes; packet should not be dropped");
215 return false;
216 }
217 okToDrop = false;
218 if (m_firstAboveTime == 0)
219 {
220 /* just went above from below. If we stay above
221 * for at least q->interval we'll say it's ok to drop
222 */
223 NS_LOG_LOGIC ("Sojourn time has just gone above target from below, need to stay above for at least q->interval before packet can be dropped. ");
225 }
226 else if (CoDelTimeAfter (now, m_firstAboveTime))
227 {
228 NS_LOG_LOGIC ("Sojourn time has been above target for at least q->interval; it's OK to (possibly) drop packet.");
229 okToDrop = true;
230 }
231 return okToDrop;
232}
233
236{
237 NS_LOG_FUNCTION (this);
238
239 Ptr<QueueDiscItem> item = GetInternalQueue (0)->Dequeue ();
240 if (!item)
241 {
242 // Leave dropping state when queue is empty
243 m_dropping = false;
244 NS_LOG_LOGIC ("Queue empty");
245 return 0;
246 }
247 uint32_t ldelay = Time2CoDel (Simulator::Now () - item->GetTimeStamp ());
248 if (item && m_useL4s)
249 {
250 uint8_t tosByte = 0;
251 if (item->GetUint8Value (QueueItem::IP_DSFIELD, tosByte) && (((tosByte & 0x3) == 1) || (tosByte & 0x3) == 3))
252 {
253 if ((tosByte & 0x3) == 1)
254 {
255 NS_LOG_DEBUG ("ECT1 packet " << static_cast<uint16_t> (tosByte & 0x3));
256 }
257 else
258 {
259 NS_LOG_DEBUG ("CE packet " << static_cast<uint16_t> (tosByte & 0x3));
260 }
261
263 {
264 NS_LOG_LOGIC ("Marking due to CeThreshold " << m_ceThreshold.GetSeconds ());
265 }
266 return item;
267 }
268 }
269
270 uint32_t now = CoDelGetTime ();
271
272 NS_LOG_LOGIC ("Popped " << item);
273 NS_LOG_LOGIC ("Number packets remaining " << GetInternalQueue (0)->GetNPackets ());
274 NS_LOG_LOGIC ("Number bytes remaining " << GetInternalQueue (0)->GetNBytes ());
275
276 // Determine if item should be dropped
277 bool okToDrop = OkToDrop (item, now);
278 bool isMarked = false;
279
280 if (m_dropping)
281 { // In the dropping state (sojourn time has gone above target and hasn't come down yet)
282 // Check if we can leave the dropping state or next drop should occur
283 NS_LOG_LOGIC ("In dropping state, check if it's OK to leave or next drop should occur");
284 if (!okToDrop)
285 {
286 /* sojourn time fell below target - leave dropping state */
287 NS_LOG_LOGIC ("Sojourn time goes below target, it's OK to leave dropping state.");
288 m_dropping = false;
289 }
290 else if (CoDelTimeAfterEq (now, m_dropNext))
291 {
292 while (m_dropping && CoDelTimeAfterEq (now, m_dropNext))
293 {
294 ++m_count;
296 // It's time for the next drop. Drop the current packet and
297 // dequeue the next. The dequeue might take us out of dropping
298 // state. If not, schedule the next drop.
299 // A large amount of packets in queue might result in drop
300 // rates so high that the next drop should happen now,
301 // hence the while loop.
302 if (m_useEcn && Mark (item, TARGET_EXCEEDED_MARK))
303 {
304 isMarked = true;
305 NS_LOG_LOGIC ("Sojourn time is still above target and it's time for next drop or mark; marking " << item);
306 NS_LOG_LOGIC ("Running ControlLaw for input m_dropNext: " << (double)m_dropNext / 1000000);
308 NS_LOG_LOGIC ("Scheduled next drop at " << (double) m_dropNext / 1000000);
309 goto end;
310 }
311 NS_LOG_LOGIC ("Sojourn time is still above target and it's time for next drop; dropping " << item);
313
314 item = GetInternalQueue (0)->Dequeue ();
315
316 if (item)
317 {
318 NS_LOG_LOGIC ("Popped " << item);
319 NS_LOG_LOGIC ("Number packets remaining " << GetInternalQueue (0)->GetNPackets ());
320 NS_LOG_LOGIC ("Number bytes remaining " << GetInternalQueue (0)->GetNBytes ());
321 }
322
323 if (!OkToDrop (item, now))
324 {
325 /* leave dropping state */
326 NS_LOG_LOGIC ("Leaving dropping state");
327 m_dropping = false;
328 }
329 else
330 {
331 /* schedule the next drop */
332 NS_LOG_LOGIC ("Running ControlLaw for input m_dropNext: " << (double)m_dropNext / 1000000);
334 NS_LOG_LOGIC ("Scheduled next drop at " << (double)m_dropNext / 1000000);
335 }
336 }
337 }
338 }
339 else
340 {
341 // Not in the dropping state
342 // Decide if we have to enter the dropping state and drop the first packet
343 NS_LOG_LOGIC ("Not in dropping state; decide if we have to enter the state and drop the first packet");
344 if (okToDrop)
345 {
346 if (m_useEcn && Mark (item, TARGET_EXCEEDED_MARK))
347 {
348 isMarked = true;
349 NS_LOG_LOGIC ("Sojourn time goes above target, marking the first packet " << item << " and entering the dropping state");
350 }
351 else
352 {
353 // Drop the first packet and enter dropping state unless the queue is empty
354 NS_LOG_LOGIC ("Sojourn time goes above target, dropping the first packet " << item << " and entering the dropping state");
356 item = GetInternalQueue (0)->Dequeue ();
357 if (item)
358 {
359 NS_LOG_LOGIC ("Popped " << item);
360 NS_LOG_LOGIC ("Number packets remaining " << GetInternalQueue (0)->GetNPackets ());
361 NS_LOG_LOGIC ("Number bytes remaining " << GetInternalQueue (0)->GetNBytes ());
362 }
363 OkToDrop (item, now);
364 }
365 m_dropping = true;
366 /*
367 * if min went above target close to when we last went below it
368 * assume that the drop rate that controlled the queue on the
369 * last cycle is a good starting point to control it now.
370 */
371 int delta = m_count - m_lastCount;
372 if (delta > 1 && CoDelTimeBefore (now - m_dropNext, 16 * Time2CoDel (m_interval)))
373 {
374 m_count = delta;
376 }
377 else
378 {
379 m_count = 1;
381 }
383 NS_LOG_LOGIC ("Running ControlLaw for input now: " << (double)now);
385 NS_LOG_LOGIC ("Scheduled next drop at " << (double)m_dropNext / 1000000 << " now " << (double)now / 1000000);
386 }
387 }
388 end:
389 ldelay = Time2CoDel (Simulator::Now () - item->GetTimeStamp ());
390 // In Linux, this branch of code is executed even if the packet has been marked
391 // according to the target delay above. If the ns-3 code were to do the same here,
392 // it would result in two counts of mark in the queue statistics. Therefore, we
393 // use the isMarked flag to suppress a second attempt at marking.
394 if (!isMarked && item && !m_useL4s && m_useEcn && CoDelTimeAfter (ldelay, Time2CoDel (m_ceThreshold)) && Mark (item, CE_THRESHOLD_EXCEEDED_MARK))
395 {
396 NS_LOG_LOGIC ("Marking due to CeThreshold " << m_ceThreshold.GetSeconds ());
397 }
398 return item;
399}
400
401Time
403{
404 return m_target;
405}
406
407Time
409{
410 return m_interval;
411}
412
415{
416 return m_dropNext;
417}
418
419bool
421{
422 return ((int64_t)(a) - (int64_t)(b) > 0);
423}
424
425bool
427{
428 return ((int64_t)(a) - (int64_t)(b) >= 0);
429}
430
431bool
433{
434 return ((int64_t)(a) - (int64_t)(b) < 0);
435}
436
437bool
439{
440 return ((int64_t)(a) - (int64_t)(b) <= 0);
441}
442
445{
446 return static_cast<uint32_t>(t.GetNanoSeconds () >> CODEL_SHIFT);
447}
448
449bool
451{
452 NS_LOG_FUNCTION (this);
453 if (GetNQueueDiscClasses () > 0)
454 {
455 NS_LOG_ERROR ("CoDelQueueDisc cannot have classes");
456 return false;
457 }
458
459 if (GetNPacketFilters () > 0)
460 {
461 NS_LOG_ERROR ("CoDelQueueDisc cannot have packet filters");
462 return false;
463 }
464
465 if (GetNInternalQueues () == 0)
466 {
467 // add a DropTail queue
469 ("MaxSize", QueueSizeValue (GetMaxSize ())));
470 }
471
472 if (GetNInternalQueues () != 1)
473 {
474 NS_LOG_ERROR ("CoDelQueueDisc needs 1 internal queue");
475 return false;
476 }
477
478 return true;
479}
480
481void
483{
484 NS_LOG_FUNCTION (this);
485}
486
487} // namespace ns3
488
AttributeValue implementation for Boolean.
Definition: boolean.h:37
A CoDel packet queue disc.
virtual void InitializeParams(void)
Initialize parameters (if any) before the first packet is enqueued.
virtual bool DoEnqueue(Ptr< QueueDiscItem > item)
Add a packet to the queue.
uint32_t GetDropNext(void)
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.
Time m_ceThreshold
Threshold above which to CE mark.
uint32_t m_minBytes
Minimum bytes in queue to allow a packet drop.
virtual bool CheckConfig(void)
Check whether the current configuration is correct.
bool CoDelTimeAfterEq(uint32_t a, uint32_t b)
Check if CoDel time a is successive or equal to b.
virtual Ptr< QueueDiscItem > DoDequeue(void)
Remove a packet from queue based on the current state If we are in dropping state,...
static constexpr const char * CE_THRESHOLD_EXCEEDED_MARK
Sojourn time above CE threshold.
Time GetInterval(void)
Get the interval.
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
Time GetTarget(void)
Get the 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.
bool m_useEcn
True if ECN is used (packets are marked instead of being dropped)
static TypeId GetTypeId(void)
Get the type ID.
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.
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.
Introspection did not find any typical Config paths.
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:78
QueueDisc is an abstract base class providing the interface and implementing the operations common to...
Definition: queue-disc.h:181
void AddInternalQueue(Ptr< InternalQueue > queue)
Add an internal queue to the tail of the list of queues.
Definition: queue-disc.cc:579
QueueSize GetCurrentSize(void)
Get the current size of the queue disc in bytes, if operating in bytes mode, or packets,...
Definition: queue-disc.cc:521
uint32_t GetNBytes(void) const
Get the amount of bytes stored by the queue disc.
Definition: queue-disc.cc:445
QueueSize GetMaxSize(void) const
Get the maximum size of the queue disc.
Definition: queue-disc.cc:452
Ptr< InternalQueue > GetInternalQueue(std::size_t i) const
Get the i-th internal queue.
Definition: queue-disc.cc:599
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.
Definition: queue-disc.cc:766
std::size_t GetNPacketFilters(void) const
Get the number of packet filters.
Definition: queue-disc.cc:626
uint32_t GetNPackets(void) const
Get the number of packets stored by the queue disc.
Definition: queue-disc.cc:438
std::size_t GetNQueueDiscClasses(void) const
Get the number of queue disc classes.
Definition: queue-disc.cc:667
bool SetMaxSize(QueueSize size)
Set the maximum size of the queue disc.
Definition: queue-disc.cc:480
std::size_t GetNInternalQueues(void) const
Get the number of internal queues.
Definition: queue-disc.cc:606
bool Mark(Ptr< QueueDiscItem > item, const char *reason)
Marks the given packet and, if successful, updates the counters associated with the given reason.
Definition: queue-disc.cc:816
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.
Definition: queue-disc.cc:727
Class for representing queue sizes.
Definition: queue-size.h:95
AttributeValue implementation for QueueSize.
static Time Now(void)
Return the current simulation virtual time.
Definition: simulator.cc:195
Hold variables of type string.
Definition: string.h:41
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:104
double GetSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:380
@ MS
millisecond
Definition: nstime.h:116
static Time Max()
Maximum representable Time Not to be confused with Max(Time,Time).
Definition: nstime.h:283
TimeWithUnit As(const enum Unit unit=Time::AUTO) const
Attach a unit to a Time, to facilitate output in a specific unit.
Definition: time.cc:418
int64_t GetNanoSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:392
AttributeValue implementation for Time.
Definition: nstime.h:1309
a unique identifier for an interface.
Definition: type-id.h:59
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:922
Hold an unsigned integer type.
Definition: uinteger.h:44
#define DEFAULT_CODEL_LIMIT
#define REC_INV_SQRT_SHIFT
Ptr< const AttributeChecker > MakeBooleanChecker(void)
Definition: boolean.cc:121
Ptr< const AttributeAccessor > MakeBooleanAccessor(T1 a1)
Definition: boolean.h:85
Ptr< const AttributeAccessor > MakeTimeAccessor(T1 a1)
Definition: nstime.h:1310
Ptr< const AttributeAccessor > MakeUintegerAccessor(T1 a1)
Definition: uinteger.h:45
#define NS_LOG_ERROR(msg)
Use NS_LOG to output a message of level LOG_ERROR.
Definition: log.h:258
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:206
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:274
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:290
#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:282
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:45
@ BYTES
Use number of bytes for queue size.
Definition: queue-size.h:45
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:104
@ SINGLE_INTERNAL_QUEUE
Used by queue discs with single internal queue.
Definition: queue-disc.h:105
Every class exported by the ns3 library is enclosed in the ns3 namespace.
static int64_t CoDelGetTime(void)
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 > MakeTimeChecker(const Time min, const Time max)
Helper to make a Time checker with bounded range.
Definition: time.cc:522
static uint32_t ReciprocalDivide(uint32_t A, uint32_t R)
Performs a reciprocal divide, similar to the Linux kernel reciprocal_divide function.