A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
cobalt-queue-disc.cc
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#include "cobalt-queue-disc.h"
17
18#include "ns3/abort.h"
19#include "ns3/drop-tail-queue.h"
20#include "ns3/enum.h"
21#include "ns3/log.h"
22#include "ns3/net-device-queue-interface.h"
23#include "ns3/object-factory.h"
24#include "ns3/uinteger.h"
25
26#include <climits>
27
28namespace ns3
29{
30
31NS_LOG_COMPONENT_DEFINE("CobaltQueueDisc");
32
33NS_OBJECT_ENSURE_REGISTERED(CobaltQueueDisc);
34
35TypeId
37{
38 static TypeId tid =
39 TypeId("ns3::CobaltQueueDisc")
41 .SetGroupName("TrafficControl")
42 .AddConstructor<CobaltQueueDisc>()
43 .AddAttribute(
44 "MaxSize",
45 "The maximum number of packets/bytes accepted by this queue disc.",
49 .AddAttribute("Interval",
50 "The Cobalt algorithm interval",
51 StringValue("100ms"),
54 .AddAttribute("Target",
55 "The Cobalt algorithm target queue delay",
56 StringValue("5ms"),
59 .AddAttribute("UseEcn",
60 "True to use ECN (packets are marked instead of being dropped)",
61 BooleanValue(false),
64 .AddAttribute("Pdrop",
65 "Marking Probability",
66 DoubleValue(0),
69 .AddAttribute("Increment",
70 "Pdrop increment value",
71 DoubleValue(1. / 256),
74 .AddAttribute("Decrement",
75 "Pdrop decrement Value",
76 DoubleValue(1. / 4096),
79 .AddAttribute("CeThreshold",
80 "The CoDel CE threshold for marking packets",
84 .AddAttribute("UseL4s",
85 "True to use L4S (only ECT1 packets are marked at CE threshold)",
86 BooleanValue(false),
89 .AddAttribute("BlueThreshold",
90 "The Threshold after which Blue is enabled",
94 .AddTraceSource("Count",
95 "Cobalt count",
97 "ns3::TracedValueCallback::Uint32")
98 .AddTraceSource("DropState",
99 "Dropping state",
101 "ns3::TracedValueCallback::Bool")
102 .AddTraceSource("DropNext",
103 "Time until next packet drop",
105 "ns3::TracedValueCallback::Uint32");
106
107 return tid;
108}
109
110/**
111 * Performs a reciprocal divide, similar to the
112 * Linux kernel reciprocal_divide function
113 * \param A numerator
114 * \param R reciprocal of the denominator B
115 * \return the value of A/B
116 */
117/* borrowed from the linux kernel */
118static inline uint32_t
120{
121 return (uint32_t)(((uint64_t)A * R) >> 32);
122}
123
124/**
125 * Returns the current time translated in CoDel time representation
126 * \return the current time
127 */
128static int64_t
130{
131 Time time = Simulator::Now();
132 int64_t ns = time.GetNanoSeconds();
133
134 return ns;
135}
136
144
145double
147{
148 return m_pDrop;
149}
150
155
156int64_t
158{
159 NS_LOG_FUNCTION(this << stream);
160 m_uv->SetStream(stream);
161 return 1;
162}
163
164void
166{
167 // Cobalt parameters
168 NS_LOG_FUNCTION(this);
169 m_recInvSqrtCache[0] = ~0;
170 CacheInit();
171 m_count = 0;
172 m_dropping = false;
173 m_recInvSqrt = ~0U;
175 m_dropNext = 0;
176}
177
178bool
180{
181 return ((int64_t)(a) - (int64_t)(b) > 0);
182}
183
184bool
186{
187 return ((int64_t)(a) - (int64_t)(b) >= 0);
188}
189
190int64_t
192{
193 return (t.GetNanoSeconds());
194}
195
196Time
198{
199 return m_target;
200}
201
202Time
204{
205 return m_interval;
206}
207
208int64_t
210{
211 return m_dropNext;
212}
213
214void
216{
217 NS_LOG_FUNCTION(this);
218 uint32_t invsqrt = ((uint32_t)m_recInvSqrt);
219 uint32_t invsqrt2 = ((uint64_t)invsqrt * invsqrt) >> 32;
220 uint64_t val = (3LL << 32) - ((uint64_t)m_count * invsqrt2);
221
222 val >>= 2; /* avoid overflow */
223 val = (val * invsqrt) >> (32 - 2 + 1);
224 m_recInvSqrt = val;
225}
226
227void
242
243void
245{
247 {
249 }
250 else
251 {
252 NewtonStep();
253 }
254}
255
256int64_t
262
263void
265{
266 NS_LOG_FUNCTION(this);
267 m_uv = nullptr;
269}
270
273{
274 NS_LOG_FUNCTION(this);
275 if (GetInternalQueue(0)->IsEmpty())
276 {
277 NS_LOG_LOGIC("Queue empty");
278 return nullptr;
279 }
280
282
283 NS_LOG_LOGIC("Number packets " << GetInternalQueue(0)->GetNPackets());
284 NS_LOG_LOGIC("Number bytes " << GetInternalQueue(0)->GetNBytes());
285
286 return item;
287}
288
289bool
291{
292 NS_LOG_FUNCTION(this);
293 if (GetNQueueDiscClasses() > 0)
294 {
295 NS_LOG_ERROR("CobaltQueueDisc cannot have classes");
296 return false;
297 }
298
299 if (GetNPacketFilters() > 0)
300 {
301 NS_LOG_ERROR("CobaltQueueDisc cannot have packet filters");
302 return false;
303 }
304
305 if (GetNInternalQueues() == 0)
306 {
310 }
311
312 if (GetNInternalQueues() != 1)
313 {
314 NS_LOG_ERROR("CobaltQueueDisc needs 1 internal queue");
315 return false;
316 }
317 return true;
318}
319
320bool
322{
323 NS_LOG_FUNCTION(this << item);
324 Ptr<Packet> p = item->GetPacket();
325 if (GetCurrentSize() + item > GetMaxSize())
326 {
327 NS_LOG_LOGIC("Queue full -- dropping pkt");
328 int64_t now = CoDelGetTime();
329 // Call this to update Blue's drop probability
330 CobaltQueueFull(now);
332 return false;
333 }
334
335 bool retval = GetInternalQueue(0)->Enqueue(item);
336
337 // If Queue::Enqueue fails, QueueDisc::Drop is called by the internal queue
338 // because QueueDisc::AddInternalQueue sets the drop callback
339
340 NS_LOG_LOGIC("Number packets " << GetInternalQueue(0)->GetNPackets());
341 NS_LOG_LOGIC("Number bytes " << GetInternalQueue(0)->GetNBytes());
342
343 return retval;
344}
345
348{
349 NS_LOG_FUNCTION(this);
350
351 while (true)
352 {
353 Ptr<QueueDiscItem> item = GetInternalQueue(0)->Dequeue();
354 if (!item)
355 {
356 // Leave dropping state when queue is empty (derived from Codel)
357 m_dropping = false;
358 NS_LOG_LOGIC("Queue empty");
359 int64_t now = CoDelGetTime();
360 // Call this to update Blue's drop probability
361 CobaltQueueEmpty(now);
362 return nullptr;
363 }
364
365 int64_t now = CoDelGetTime();
366
367 NS_LOG_LOGIC("Popped " << item);
368 NS_LOG_LOGIC("Number packets remaining " << GetInternalQueue(0)->GetNPackets());
369 NS_LOG_LOGIC("Number bytes remaining " << GetInternalQueue(0)->GetNBytes());
370
371 // Determine if item should be dropped
372 // ECN marking happens inside this function, so it need not be done here
373 bool drop = CobaltShouldDrop(item, now);
374
375 if (drop)
376 {
378 }
379 else
380 {
381 return item;
382 }
383 }
384}
385
386// Call this when a packet had to be dropped due to queue overflow.
387void
389{
390 NS_LOG_FUNCTION(this);
391 NS_LOG_LOGIC("Outside IF block");
393 {
394 NS_LOG_LOGIC("inside IF block");
395 m_pDrop = std::min(m_pDrop + m_increment, 1.0);
397 }
398 m_dropping = true;
399 m_dropNext = now;
400 if (!m_count)
401 {
402 m_count = 1;
403 }
404}
405
406// Call this when the queue was serviced but turned out to be empty.
407void
409{
410 NS_LOG_FUNCTION(this);
412 {
413 m_pDrop = std::max(m_pDrop - m_decrement, 0.0);
415 }
416 m_dropping = false;
417
418 if (m_count && CoDelTimeAfterEq((now - m_dropNext), 0))
419 {
420 m_count--;
421 InvSqrt();
423 }
424}
425
426// Determines if Cobalt should drop the packet
427bool
429{
430 NS_LOG_FUNCTION(this);
431 bool drop = false;
432
433 /* Simplified Codel implementation */
434 Time delta = Simulator::Now() - item->GetTimeStamp();
435 NS_LOG_INFO("Sojourn time " << delta.As(Time::S));
436 int64_t sojournTime = Time2CoDel(delta);
437 int64_t schedule = now - m_dropNext;
438 bool over_target = CoDelTimeAfter(sojournTime, Time2CoDel(m_target));
439 bool next_due = m_count && schedule >= 0;
440 bool isMarked = false;
441
442 // If L4S mode is enabled then check if the packet is ECT1 or CE and
443 // if sojourn time is greater than CE threshold then the packet is marked.
444 // If packet is marked successfully then the CoDel steps can be skipped.
445 if (item && m_useL4s)
446 {
447 uint8_t tosByte = 0;
448 if (item->GetUint8Value(QueueItem::IP_DSFIELD, tosByte) &&
449 (((tosByte & 0x3) == 1) || (tosByte & 0x3) == 3))
450 {
451 if ((tosByte & 0x3) == 1)
452 {
453 NS_LOG_DEBUG("ECT1 packet " << static_cast<uint16_t>(tosByte & 0x3));
454 }
455 else
456 {
457 NS_LOG_DEBUG("CE packet " << static_cast<uint16_t>(tosByte & 0x3));
458 }
459 if (CoDelTimeAfter(sojournTime, Time2CoDel(m_ceThreshold)) &&
461 {
462 NS_LOG_LOGIC("Marking due to CeThreshold " << m_ceThreshold.GetSeconds());
463 }
464 return false;
465 }
466 }
467
468 if (over_target)
469 {
470 if (!m_dropping)
471 {
472 m_dropping = true;
473 m_dropNext = ControlLaw(now);
474 }
475 if (!m_count)
476 {
477 m_count = 1;
478 }
479 }
480 else if (m_dropping)
481 {
482 m_dropping = false;
483 }
484
485 if (next_due && m_dropping)
486 {
487 /* Check for marking possibility only if BLUE decides NOT to drop. */
488 /* Check if router and packet, both have ECN enabled. Only if this is true, mark the packet.
489 */
490 isMarked = (m_useEcn && Mark(item, FORCED_MARK));
491 drop = !isMarked;
492
493 m_count = std::max(m_count, m_count + 1);
494
495 InvSqrt();
497 schedule = now - m_dropNext;
498 }
499 else
500 {
501 while (next_due)
502 {
503 m_count--;
504 InvSqrt();
506 schedule = now - m_dropNext;
507 next_due = m_count && schedule >= 0;
508 }
509 }
510
511 // If CE threshold is enabled then isMarked flag is used to determine whether
512 // packet is marked and if the packet is marked then a second attempt at marking should be
513 // suppressed. If UseL4S attribute is enabled then ECT0 packets should not be marked.
514 if (!isMarked && !m_useL4s && m_useEcn &&
515 CoDelTimeAfter(sojournTime, Time2CoDel(m_ceThreshold)) &&
517 {
518 NS_LOG_LOGIC("Marking due to CeThreshold " << m_ceThreshold.GetSeconds());
519 }
520
521 // Enable Blue Enhancement if sojourn time is greater than blueThreshold and its been m_target
522 // time until the last time blue was updated
523 if (CoDelTimeAfter(sojournTime, Time2CoDel(m_blueThreshold)) &&
525 {
526 m_pDrop = std::min(m_pDrop + m_increment, 1.0);
528 }
529
530 /* Simple BLUE implementation. Lack of ECN is deliberate. */
531 if (m_pDrop)
532 {
533 double u = m_uv->GetValue();
534 drop = drop || (u < m_pDrop);
535 }
536
537 /* Overload the drop_next field as an activity timeout */
538 if (!m_count)
539 {
541 }
542 else if (schedule > 0 && !drop)
543 {
544 m_dropNext = now;
545 }
546
547 return drop;
548}
549
550} // namespace ns3
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.
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)
This class can be used to hold variables of floating point type such as 'double' or 'float'.
Definition double.h:31
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.
void DoDispose() override
Dispose of the object.
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
@ S
second
Definition nstime.h:105
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
#define DEFAULT_COBALT_LIMIT
#define REC_INV_SQRT_CACHE
#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(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 > CreateObject(Args &&... args)
Create an object by type, with varying number of constructor parameters.
Definition object.h:619
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
Time MilliSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition nstime.h:1320
Ptr< const TraceSourceAccessor > MakeTraceSourceAccessor(T a)
Create a TraceSourceAccessor which will control access to the underlying trace source.
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 AttributeAccessor > MakeTimeAccessor(T1 a1)
Definition nstime.h:1396
Ptr< const AttributeChecker > MakeDoubleChecker()
Definition double.h:82
static int64_t CoDelGetTime()
Returns the current time translated in CoDel 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 AttributeAccessor > MakeDoubleAccessor(T1 a1)
Definition double.h:32
Ptr< const AttributeChecker > MakeTimeChecker()
Helper to make an unbounded Time checker.
Definition nstime.h:1416