A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
pie-queue-disc.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2016 NITK Surathkal
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Authors: Shravya Ks <shravya.ks0@gmail.com>
7 * Smriti Murali <m.smriti.95@gmail.com>
8 * Mohit P. Tahiliani <tahiliani@nitk.edu.in>
9 */
10
11/*
12 * PORT NOTE: This code was ported from ns-2.36rc1 (queue/pie.cc).
13 * Most of the comments are also ported from the same.
14 */
15
16#include "pie-queue-disc.h"
17
18#include "ns3/abort.h"
19#include "ns3/double.h"
20#include "ns3/drop-tail-queue.h"
21#include "ns3/enum.h"
22#include "ns3/log.h"
23#include "ns3/simulator.h"
24#include "ns3/uinteger.h"
25
26namespace ns3
27{
28
29NS_LOG_COMPONENT_DEFINE("PieQueueDisc");
30
31NS_OBJECT_ENSURE_REGISTERED(PieQueueDisc);
32
33TypeId
35{
36 static TypeId tid =
37 TypeId("ns3::PieQueueDisc")
39 .SetGroupName("TrafficControl")
40 .AddConstructor<PieQueueDisc>()
41 .AddAttribute("MeanPktSize",
42 "Average of packet size",
43 UintegerValue(1000),
46 .AddAttribute("A",
47 "Value of alpha",
48 DoubleValue(0.125),
51 .AddAttribute("B",
52 "Value of beta",
53 DoubleValue(1.25),
56 .AddAttribute("Tupdate",
57 "Time period to calculate drop probability",
61 .AddAttribute("Supdate",
62 "Start time of the update timer",
66 .AddAttribute("MaxSize",
67 "The maximum number of packets accepted by this queue disc",
71 .AddAttribute("DequeueThreshold",
72 "Minimum queue size in bytes before dequeue rate is measured",
73 UintegerValue(16384),
76 .AddAttribute("QueueDelayReference",
77 "Desired queue delay",
81 .AddAttribute("MaxBurstAllowance",
82 "Current max burst allowance before random drop",
86 .AddAttribute("UseDequeueRateEstimator",
87 "Enable/Disable usage of Dequeue Rate Estimator",
88 BooleanValue(false),
91 .AddAttribute("UseCapDropAdjustment",
92 "Enable/Disable Cap Drop Adjustment feature mentioned in RFC 8033",
93 BooleanValue(true),
96 .AddAttribute("UseEcn",
97 "True to use ECN (packets are marked instead of being dropped)",
98 BooleanValue(false),
101 .AddAttribute("MarkEcnThreshold",
102 "ECN marking threshold (RFC 8033 suggests 0.1 (i.e., 10%) default)",
103 DoubleValue(0.1),
106 .AddAttribute("UseDerandomization",
107 "Enable/Disable Derandomization feature mentioned in RFC 8033",
108 BooleanValue(false),
111 .AddAttribute("ActiveThreshold",
112 "Threshold for activating PIE (disabled by default)",
116 .AddAttribute("CeThreshold",
117 "The FqPie CE threshold for marking packets",
121 .AddAttribute("UseL4s",
122 "True to use L4S (only ECT1 packets are marked at CE threshold)",
123 BooleanValue(false),
126
127 return tid;
128}
129
137
142
143void
145{
146 NS_LOG_FUNCTION(this);
147 m_uv = nullptr;
150}
151
152Time
154{
155 return m_qDelay;
156}
157
158int64_t
160{
161 NS_LOG_FUNCTION(this << stream);
162 m_uv->SetStream(stream);
163 return 1;
164}
165
166bool
168{
169 NS_LOG_FUNCTION(this << item);
170
171 QueueSize nQueued = GetCurrentSize();
172 // If L4S is enabled, then check if the packet is ECT1, and if it is then set isEct true
173 bool isEct1 = false;
174 if (item && m_useL4s)
175 {
176 uint8_t tosByte = 0;
177 if (item->GetUint8Value(QueueItem::IP_DSFIELD, tosByte) &&
178 (((tosByte & 0x3) == 1) || (tosByte & 0x3) == 3))
179 {
180 if ((tosByte & 0x3) == 1)
181 {
182 NS_LOG_DEBUG("Enqueueing ECT1 packet " << static_cast<uint16_t>(tosByte & 0x3));
183 }
184 else
185 {
186 NS_LOG_DEBUG("Enqueueing CE packet " << static_cast<uint16_t>(tosByte & 0x3));
187 }
188 isEct1 = true;
189 }
190 }
191
192 if (nQueued + item > GetMaxSize())
193 {
194 // Drops due to queue limit: reactive
196 m_accuProb = 0;
197 return false;
198 }
199 // isEct1 will be true only if L4S enabled as well as the packet is ECT1.
200 // If L4S is enabled and packet is ECT1 then directly enqueue the packet.
201 else if ((m_activeThreshold == Time::Max() || m_active) && !isEct1 &&
202 DropEarly(item, nQueued.GetValue()))
203 {
204 if (!m_useEcn || m_dropProb >= m_markEcnTh || !Mark(item, UNFORCED_MARK))
205 {
206 // Early probability drop: proactive
208 m_accuProb = 0;
209 return false;
210 }
211 }
212
213 // No drop
214 bool retval = GetInternalQueue(0)->Enqueue(item);
215
216 // If the queue is over a certain threshold, Turn ON PIE
218 {
219 m_active = true;
220 m_qDelayOld = Seconds(0);
221 m_dropProb = 0;
222 m_inMeasurement = true;
223 m_dqCount = 0;
224 m_avgDqRate = 0;
226 m_accuProb = 0;
227 m_dqStart = Now();
228 }
229
230 // If queue has been Idle for a while, Turn OFF PIE
231 // Reset Counters when accessing the queue after some idle period if PIE was active before
234 {
235 m_active = false;
236 m_inMeasurement = false;
237 }
238
239 // If Queue::Enqueue fails, QueueDisc::DropBeforeEnqueue is called by the
240 // internal queue because QueueDisc::AddInternalQueue sets the trace callback
241
242 NS_LOG_LOGIC("\t bytesInQueue " << GetInternalQueue(0)->GetNBytes());
243 NS_LOG_LOGIC("\t packetsInQueue " << GetInternalQueue(0)->GetNPackets());
244
245 return retval;
246}
247
248void
250{
251 // Initially queue is empty so variables are initialize to zero except m_dqCount
252 m_inMeasurement = false;
254 m_dropProb = 0;
255 m_avgDqRate = 0.0;
256 m_dqStart = Seconds(0);
258 m_qDelayOld = Seconds(0);
259 m_accuProb = 0.0;
260 m_active = false;
261}
262
263bool
265{
266 NS_LOG_FUNCTION(this << item << qSize);
268 {
269 // If there is still burst_allowance left, skip random early drop.
270 return false;
271 }
272
273 if (m_burstState == NO_BURST)
274 {
277 }
278
279 double p = m_dropProb;
280
281 uint32_t packetSize = item->GetSize();
282
283 if (GetMaxSize().GetUnit() == QueueSizeUnit::BYTES)
284 {
285 p = p * packetSize / m_meanPktSize;
286 }
287
288 // Safeguard PIE to be work conserving (Section 4.1 of RFC 8033)
289 if ((m_qDelayOld.GetSeconds() < (0.5 * m_qDelayRef.GetSeconds()) && m_dropProb < 0.2) ||
290 (GetMaxSize().GetUnit() == QueueSizeUnit::BYTES && qSize <= 2 * m_meanPktSize) ||
291 (GetMaxSize().GetUnit() == QueueSizeUnit::PACKETS && qSize <= 2))
292 {
293 return false;
294 }
295
297 {
298 if (m_dropProb == 0)
299 {
300 m_accuProb = 0;
301 }
303 if (m_accuProb < 0.85)
304 {
305 return false;
306 }
307 else if (m_accuProb >= 8.5)
308 {
309 return true;
310 }
311 }
312
313 double u = m_uv->GetValue();
314 return u <= p;
315}
316
317void
319{
320 NS_LOG_FUNCTION(this);
321 Time qDelay;
322 double p = 0.0;
323 bool missingInitFlag = false;
324
326 {
327 if (m_avgDqRate > 0)
328 {
330 }
331 else
332 {
333 qDelay = Seconds(0);
334 missingInitFlag = true;
335 }
336 m_qDelay = qDelay;
337 }
338 else
339 {
340 qDelay = m_qDelay;
341 }
342 NS_LOG_DEBUG("Queue delay while calculating probability: " << qDelay.GetMilliSeconds() << "ms");
343
345 {
346 m_dropProb = 0;
347 }
348 else
349 {
350 p = m_a * (qDelay.GetSeconds() - m_qDelayRef.GetSeconds()) +
351 m_b * (qDelay.GetSeconds() - m_qDelayOld.GetSeconds());
352 if (m_dropProb < 0.000001)
353 {
354 p /= 2048;
355 }
356 else if (m_dropProb < 0.00001)
357 {
358 p /= 512;
359 }
360 else if (m_dropProb < 0.0001)
361 {
362 p /= 128;
363 }
364 else if (m_dropProb < 0.001)
365 {
366 p /= 32;
367 }
368 else if (m_dropProb < 0.01)
369 {
370 p /= 8;
371 }
372 else if (m_dropProb < 0.1)
373 {
374 p /= 2;
375 }
376 else
377 {
378 // The pseudocode in Section 4.2 of RFC 8033 suggests to use this for
379 // assignment of p, but this assignment causes build failure on Mac OS
380 // p = p;
381 }
382
383 // Cap Drop Adjustment (Section 5.5 of RFC 8033)
384 if (m_isCapDropAdjustment && (m_dropProb >= 0.1) && (p > 0.02))
385 {
386 p = 0.02;
387 }
388 }
389
390 p += m_dropProb;
391
392 // For non-linear drop in prob
393 // Decay the drop probability exponentially (Section 4.2 of RFC 8033)
394 if (qDelay.GetSeconds() == 0 && m_qDelayOld.GetSeconds() == 0)
395 {
396 p *= 0.98;
397 }
398
399 // bound the drop probability (Section 4.2 of RFC 8033)
400 if (p < 0)
401 {
402 m_dropProb = 0;
403 }
404 else if (p > 1)
405 {
406 m_dropProb = 1;
407 }
408 else
409 {
410 m_dropProb = p;
411 }
412
413 // Section 4.4 #2
415 {
417 }
418 else
419 {
421 }
422
423 auto burstResetLimit = static_cast<uint32_t>(BURST_RESET_TIMEOUT / m_tUpdate.GetSeconds());
424 if ((qDelay.GetSeconds() < 0.5 * m_qDelayRef.GetSeconds()) &&
425 (m_qDelayOld.GetSeconds() < (0.5 * m_qDelayRef.GetSeconds())) && (m_dropProb == 0) &&
426 !missingInitFlag)
427 {
429 m_avgDqRate = 0.0;
430 }
431 if ((qDelay.GetSeconds() < 0.5 * m_qDelayRef.GetSeconds()) &&
432 (m_qDelayOld.GetSeconds() < (0.5 * m_qDelayRef.GetSeconds())) && (m_dropProb == 0) &&
434 {
436 {
438 m_burstReset = 0;
439 }
440 else if (m_burstState == IN_BURST)
441 {
442 m_burstReset++;
443 if (m_burstReset > burstResetLimit)
444 {
445 m_burstReset = 0;
447 }
448 }
449 }
450 else if (m_burstState == IN_BURST)
451 {
452 m_burstReset = 0;
453 }
454
455 m_qDelayOld = qDelay;
457}
458
461{
462 NS_LOG_FUNCTION(this);
463
464 if (GetInternalQueue(0)->IsEmpty())
465 {
466 NS_LOG_LOGIC("Queue empty");
467 return nullptr;
468 }
469
470 Ptr<QueueDiscItem> item = GetInternalQueue(0)->Dequeue();
471 NS_ASSERT_MSG(item, "Dequeue null, but internal queue not empty");
472
473 // If L4S is enabled and packet is ECT1, then check if delay is greater
474 // than CE threshold and if it is then mark the packet,
475 // skip PIE steps, and return the item.
476 if (m_useL4s)
477 {
478 uint8_t tosByte = 0;
479 if (item->GetUint8Value(QueueItem::IP_DSFIELD, tosByte) &&
480 (((tosByte & 0x3) == 1) || (tosByte & 0x3) == 3))
481 {
482 if ((tosByte & 0x3) == 1)
483 {
484 NS_LOG_DEBUG("ECT1 packet " << static_cast<uint16_t>(tosByte & 0x3));
485 }
486 else
487 {
488 NS_LOG_DEBUG("CE packet " << static_cast<uint16_t>(tosByte & 0x3));
489 }
490 if ((Now() - item->GetTimeStamp() > m_ceThreshold) &&
492 {
493 NS_LOG_LOGIC("Marking due to CeThreshold " << m_ceThreshold.GetSeconds());
494 }
495 return item;
496 }
497 }
498
499 // if not in a measurement cycle and the queue has built up to dq_threshold,
500 // start the measurement cycle
502 {
504 {
505 m_dqStart = Now();
506 m_dqCount = 0;
507 m_inMeasurement = true;
508 }
509
510 if (m_inMeasurement)
511 {
512 m_dqCount += item->GetSize();
513
514 // done with a measurement cycle
516 {
517 Time dqTime = Now() - m_dqStart;
518 if (dqTime > Seconds(0))
519 {
520 if (m_avgDqRate == 0)
521 {
522 m_avgDqRate = m_dqCount / dqTime.GetSeconds();
523 }
524 else
525 {
527 (0.5 * m_avgDqRate) + (0.5 * (m_dqCount / dqTime.GetSeconds()));
528 }
529 }
530 NS_LOG_DEBUG("Average Dequeue Rate after Dequeue: " << m_avgDqRate);
531
532 // restart a measurement cycle if there is enough data
534 {
535 m_dqStart = Now();
536 m_dqCount = 0;
537 m_inMeasurement = true;
538 }
539 else
540 {
541 m_dqCount = 0;
542 m_inMeasurement = false;
543 }
544 }
545 }
546 }
547 else
548 {
549 m_qDelay = Now() - item->GetTimeStamp();
550
551 if (GetInternalQueue(0)->GetNBytes() == 0)
552 {
553 m_qDelay = Seconds(0);
554 }
555 }
556 return item;
557}
558
559bool
561{
562 NS_LOG_FUNCTION(this);
563 if (GetNQueueDiscClasses() > 0)
564 {
565 NS_LOG_ERROR("PieQueueDisc cannot have classes");
566 return false;
567 }
568
569 if (GetNPacketFilters() > 0)
570 {
571 NS_LOG_ERROR("PieQueueDisc cannot have packet filters");
572 return false;
573 }
574
575 if (GetNInternalQueues() == 0)
576 {
577 // add a DropTail queue
581 }
582
583 if (GetNInternalQueues() != 1)
584 {
585 NS_LOG_ERROR("PieQueueDisc needs 1 internal queue");
586 return false;
587 }
588
589 return true;
590}
591
592} // namespace ns3
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.
void Cancel()
This method is syntactic sugar for the ns3::Simulator::Cancel method.
Definition event-id.cc:44
Implements PIE Active Queue Management discipline.
uint32_t m_dqThreshold
Minimum queue size in bytes before dequeue rate is measured.
uint32_t m_meanPktSize
Average packet size in bytes.
double m_markEcnTh
ECN marking threshold (default 10% as suggested in RFC 8033)
bool m_useDqRateEstimator
Enable/Disable usage of dequeue rate estimator for queue delay calculation.
bool DoEnqueue(Ptr< QueueDiscItem > item) override
This function actually enqueues a packet into the queue disc.
void DoDispose() override
Dispose of the object.
bool m_useL4s
True if L4S is used (ECT1 packets are marked at CE threshold)
Time m_sUpdate
Start time of the update timer.
Time m_dqStart
Start timestamp of current measurement cycle.
bool m_useDerandomization
Enable Derandomization feature mentioned in RFC 8033.
static constexpr const char * UNFORCED_DROP
Early probability drops: proactive.
Time m_maxBurst
Maximum burst allowed before random early dropping kicks in.
EventId m_rtrsEvent
Event used to decide the decision of interval of drop probability calculation.
void CalculateP()
Periodically update the drop probability based on the delay samples: not only the current delay sampl...
Time m_ceThreshold
Threshold above which to CE mark.
Time m_qDelayOld
Old value of queue delay.
double m_dropProb
Variable used in calculation of drop probability.
Time m_burstAllowance
Current max burst value in seconds that is allowed before random drops kick in.
BurstStateT m_burstState
Used to determine the current state of burst.
Time GetQueueDelay()
Get queue delay.
Ptr< QueueDiscItem > DoDequeue() override
This function actually extracts a packet from the queue disc.
bool DropEarly(Ptr< QueueDiscItem > item, uint32_t qSize)
Check if a packet needs to be dropped due to probability drop.
bool m_active
Indicates whether PIE is in active state or not.
double m_avgDqRate
Time averaged dequeue rate.
static const uint64_t DQCOUNT_INVALID
Invalid dqCount value.
uint32_t m_burstReset
Used to reset value of burst allowance.
void InitializeParams() override
Initialize the queue parameters.
bool m_inMeasurement
Indicates whether we are in a measurement cycle.
static constexpr const char * FORCED_DROP
Drops due to queue limit: reactive.
Time m_qDelayRef
Desired queue delay.
~PieQueueDisc() override
PieQueueDisc Destructor.
double m_a
Parameter to pie controller.
static constexpr const char * CE_THRESHOLD_EXCEEDED_MARK
Early probability marks: proactive.
Time m_activeThreshold
Threshold for activating PIE (disabled by default)
bool m_isCapDropAdjustment
Enable/Disable Cap Drop Adjustment feature mentioned in RFC 8033.
int64_t AssignStreams(int64_t stream)
Assign a fixed random variable stream number to the random variables used by this model.
double m_accuProb
Accumulated drop probability.
Ptr< UniformRandomVariable > m_uv
Rng stream.
bool m_useEcn
Enable ECN Marking functionality.
Time m_tUpdate
Time period after which CalculateP () is called.
PieQueueDisc()
PieQueueDisc Constructor.
bool CheckConfig() override
Check whether the current configuration is correct.
Time m_qDelay
Current value of queue delay.
uint64_t m_dqCount
Number of bytes departed since current measurement cycle starts.
static TypeId GetTypeId()
Get the type ID.
double m_b
Parameter to pie controller.
static constexpr const char * UNFORCED_MARK
Early probability marks: proactive.
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,...
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
uint32_t GetValue() const
Get the underlying value.
static EventId Schedule(const Time &delay, FUNC f, Ts &&... args)
Schedule an event to expire after delay.
Definition simulator.h:560
Simulation virtual time values and global simulation resolution.
Definition nstime.h:94
int64_t GetMilliSeconds() const
Get an approximation of the time stored in this instance in the indicated unit.
Definition nstime.h:397
double GetSeconds() const
Get an approximation of the time stored in this instance in the indicated unit.
Definition nstime.h:392
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 NS_ASSERT_MSG(condition, message)
At runtime, in debugging builds, if this condition is not true, the program prints the message to out...
Definition assert.h:75
#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 ",...
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
@ PACKETS
Use number of packets for queue size.
Definition queue-size.h:34
Time Now()
create an ns3::Time instance which contains the current simulation time.
Definition simulator.cc:294
Time Seconds(double value)
Construct a Time in the indicated unit.
Definition nstime.h:1308
Time MilliSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition nstime.h:1320
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
Ptr< const AttributeChecker > MakeDoubleChecker()
Definition double.h:82
Ptr< const AttributeChecker > MakeQueueSizeChecker()
Definition queue-size.cc:18
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
#define BURST_RESET_TIMEOUT
static const uint32_t packetSize
Packet size generated at the AP.