A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
fq-pie-queue-disc.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2016 Universita' degli Studi di Napoli Federico II
3 * Copyright (c) 2018 NITK Surathkal (modified for FQ-PIE)
4 *
5 * SPDX-License-Identifier: GPL-2.0-only
6 *
7 * Authors: Pasquale Imputato <p.imputato@gmail.com>
8 * Stefano Avallone <stefano.avallone@unina.it>
9 * Modified for FQ-PIE by: Sumukha PK <sumukhapk46@gmail.com>
10 * Prajval M <26prajval98@gmail.com>
11 * Ishaan R D <ishaanrd6@gmail.com>
12 * Mohit P. Tahiliani <tahiliani@nitk.edu.in>
13 */
14
15#include "fq-pie-queue-disc.h"
16
17#include "pie-queue-disc.h"
18
19#include "ns3/log.h"
20#include "ns3/net-device-queue-interface.h"
21#include "ns3/queue.h"
22#include "ns3/string.h"
23
24namespace ns3
25{
26
27NS_LOG_COMPONENT_DEFINE("FqPieQueueDisc");
28
30
31TypeId
33{
34 static TypeId tid = TypeId("ns3::FqPieFlow")
36 .SetGroupName("TrafficControl")
37 .AddConstructor<FqPieFlow>();
38 return tid;
39}
40
42 : m_deficit(0),
43 m_status(INACTIVE),
44 m_index(0)
45{
46 NS_LOG_FUNCTION(this);
47}
48
53
54void
56{
57 NS_LOG_FUNCTION(this << deficit);
58 m_deficit = deficit;
59}
60
63{
64 NS_LOG_FUNCTION(this);
65 return m_deficit;
66}
67
68void
70{
71 NS_LOG_FUNCTION(this << deficit);
72 m_deficit += deficit;
73}
74
75void
77{
78 NS_LOG_FUNCTION(this);
79 m_status = status;
80}
81
84{
85 NS_LOG_FUNCTION(this);
86 return m_status;
87}
88
89void
91{
92 NS_LOG_FUNCTION(this);
93 m_index = index;
94}
95
98{
99 return m_index;
100}
101
103
104TypeId
106{
107 static TypeId tid =
108 TypeId("ns3::FqPieQueueDisc")
110 .SetGroupName("TrafficControl")
111 .AddConstructor<FqPieQueueDisc>()
112 .AddAttribute("UseEcn",
113 "True to use ECN (packets are marked instead of being dropped)",
114 BooleanValue(true),
117 .AddAttribute("MarkEcnThreshold",
118 "ECN marking threshold (RFC 8033 suggests 0.1 (i.e., 10%) default)",
119 DoubleValue(0.1),
122 .AddAttribute("CeThreshold",
123 "The FqPie CE threshold for marking packets",
127 .AddAttribute("UseL4s",
128 "True to use L4S (only ECT1 packets are marked at CE threshold)",
129 BooleanValue(false),
132 .AddAttribute("MeanPktSize",
133 "Average of packet size",
134 UintegerValue(1000),
137 .AddAttribute("A",
138 "Value of alpha",
139 DoubleValue(0.125),
142 .AddAttribute("B",
143 "Value of beta",
144 DoubleValue(1.25),
147 .AddAttribute("Tupdate",
148 "Time period to calculate drop probability",
149 TimeValue(Seconds(0.015)),
152 .AddAttribute("Supdate",
153 "Start time of the update timer",
154 TimeValue(Seconds(0)),
157 .AddAttribute("MaxSize",
158 "The maximum number of packets accepted by this queue disc",
159 QueueSizeValue(QueueSize("10240p")),
162 .AddAttribute("DequeueThreshold",
163 "Minimum queue size in bytes before dequeue rate is measured",
164 UintegerValue(16384),
167 .AddAttribute("QueueDelayReference",
168 "Desired queue delay",
169 TimeValue(Seconds(0.015)),
172 .AddAttribute("MaxBurstAllowance",
173 "Current max burst allowance before random drop",
174 TimeValue(Seconds(0.15)),
177 .AddAttribute("UseDequeueRateEstimator",
178 "Enable/Disable usage of Dequeue Rate Estimator",
179 BooleanValue(false),
182 .AddAttribute("UseCapDropAdjustment",
183 "Enable/Disable Cap Drop Adjustment feature mentioned in RFC 8033",
184 BooleanValue(true),
187 .AddAttribute("UseDerandomization",
188 "Enable/Disable Derandomization feature mentioned in RFC 8033",
189 BooleanValue(false),
192 .AddAttribute("Flows",
193 "The number of queues into which the incoming packets are classified",
194 UintegerValue(1024),
197 .AddAttribute("DropBatchSize",
198 "The maximum number of packets dropped from the fat flow",
199 UintegerValue(64),
202 .AddAttribute("Perturbation",
203 "The salt used as an additional input to the hash function used to "
204 "classify packets",
205 UintegerValue(0),
208 .AddAttribute("EnableSetAssociativeHash",
209 "Enable/Disable Set Associative Hash",
210 BooleanValue(false),
213 .AddAttribute("SetWays",
214 "The size of a set of queues (used by set associative hash)",
215 UintegerValue(8),
218 return tid;
219}
220
227
232
233void
235{
236 NS_LOG_FUNCTION(this << quantum);
237 m_quantum = quantum;
238}
239
242{
243 return m_quantum;
244}
245
248{
249 NS_LOG_FUNCTION(this << flowHash);
250
251 uint32_t h = (flowHash % m_flows);
252 uint32_t innerHash = h % m_setWays;
253 uint32_t outerHash = h - innerHash;
254
255 for (uint32_t i = outerHash; i < outerHash + m_setWays; i++)
256 {
257 auto it = m_flowsIndices.find(i);
258
259 if (it == m_flowsIndices.end() ||
260 (m_tags.find(i) != m_tags.end() && m_tags[i] == flowHash) ||
261 StaticCast<FqPieFlow>(GetQueueDiscClass(it->second))->GetStatus() ==
263 {
264 // this queue has not been created yet or is associated with this flow
265 // or is inactive, hence we can use it
266 m_tags[i] = flowHash;
267 return i;
268 }
269 }
270
271 // all the queues of the set are used. Use the first queue of the set
272 m_tags[outerHash] = flowHash;
273 return outerHash;
274}
275
276bool
278{
279 NS_LOG_FUNCTION(this << item);
280
281 uint32_t flowHash;
282 uint32_t h;
283
284 if (GetNPacketFilters() == 0)
285 {
286 flowHash = item->Hash(m_perturbation);
287 }
288 else
289 {
290 int32_t ret = Classify(item);
291
292 if (ret != PacketFilter::PF_NO_MATCH)
293 {
294 flowHash = static_cast<uint32_t>(ret);
295 }
296 else
297 {
298 NS_LOG_ERROR("No filter has been able to classify this packet, drop it.");
300 return false;
301 }
302 }
303
305 {
306 h = SetAssociativeHash(flowHash);
307 }
308 else
309 {
310 h = flowHash % m_flows;
311 }
312
313 Ptr<FqPieFlow> flow;
314 if (m_flowsIndices.find(h) == m_flowsIndices.end())
315 {
316 NS_LOG_DEBUG("Creating a new flow queue with index " << h);
319 // If Pie, Set values of PieQueueDisc to match this QueueDisc
320 Ptr<PieQueueDisc> pie = qd->GetObject<PieQueueDisc>();
321 if (pie)
322 {
323 pie->SetAttribute("UseEcn", BooleanValue(m_useEcn));
324 pie->SetAttribute("CeThreshold", TimeValue(m_ceThreshold));
325 pie->SetAttribute("UseL4s", BooleanValue(m_useL4s));
326 }
327 qd->Initialize();
328 flow->SetQueueDisc(qd);
329 flow->SetIndex(h);
330 AddQueueDiscClass(flow);
331
333 }
334 else
335 {
337 }
338
339 if (flow->GetStatus() == FqPieFlow::INACTIVE)
340 {
341 flow->SetStatus(FqPieFlow::NEW_FLOW);
342 flow->SetDeficit(m_quantum);
343 m_newFlows.push_back(flow);
344 }
345
346 flow->GetQueueDisc()->Enqueue(item);
347
348 NS_LOG_DEBUG("Packet enqueued into flow " << h << "; flow index " << m_flowsIndices[h]);
349
350 if (GetCurrentSize() > GetMaxSize())
351 {
352 NS_LOG_DEBUG("Overload; enter FqPieDrop ()");
353 FqPieDrop();
354 }
355
356 return true;
357}
358
361{
362 NS_LOG_FUNCTION(this);
363
364 Ptr<FqPieFlow> flow;
366
367 do
368 {
369 bool found = false;
370
371 while (!found && !m_newFlows.empty())
372 {
373 flow = m_newFlows.front();
374
375 if (flow->GetDeficit() <= 0)
376 {
377 NS_LOG_DEBUG("Increase deficit for new flow index " << flow->GetIndex());
378 flow->IncreaseDeficit(m_quantum);
379 flow->SetStatus(FqPieFlow::OLD_FLOW);
380 m_oldFlows.push_back(flow);
381 m_newFlows.pop_front();
382 }
383 else
384 {
385 NS_LOG_DEBUG("Found a new flow " << flow->GetIndex() << " with positive deficit");
386 found = true;
387 }
388 }
389
390 while (!found && !m_oldFlows.empty())
391 {
392 flow = m_oldFlows.front();
393
394 if (flow->GetDeficit() <= 0)
395 {
396 NS_LOG_DEBUG("Increase deficit for old flow index " << flow->GetIndex());
397 flow->IncreaseDeficit(m_quantum);
398 m_oldFlows.push_back(flow);
399 m_oldFlows.pop_front();
400 }
401 else
402 {
403 NS_LOG_DEBUG("Found an old flow " << flow->GetIndex() << " with positive deficit");
404 found = true;
405 }
406 }
407
408 if (!found)
409 {
410 NS_LOG_DEBUG("No flow found to dequeue a packet");
411 return nullptr;
412 }
413
414 item = flow->GetQueueDisc()->Dequeue();
415
416 if (!item)
417 {
418 NS_LOG_DEBUG("Could not get a packet from the selected flow queue");
419 if (!m_newFlows.empty())
420 {
421 flow->SetStatus(FqPieFlow::OLD_FLOW);
422 m_oldFlows.push_back(flow);
423 m_newFlows.pop_front();
424 }
425 else
426 {
427 flow->SetStatus(FqPieFlow::INACTIVE);
428 m_oldFlows.pop_front();
429 }
430 }
431 else
432 {
433 NS_LOG_DEBUG("Dequeued packet " << item->GetPacket());
434 }
435 } while (!item);
436
437 flow->IncreaseDeficit(item->GetSize() * -1);
438
439 return item;
440}
441
442bool
444{
445 NS_LOG_FUNCTION(this);
446 if (GetNQueueDiscClasses() > 0)
447 {
448 NS_LOG_ERROR("FqPieQueueDisc cannot have classes");
449 return false;
450 }
451
452 if (GetNInternalQueues() > 0)
453 {
454 NS_LOG_ERROR("FqPieQueueDisc cannot have internal queues");
455 return false;
456 }
457 // we are at initialization time. If the user has not set a quantum value,
458 // set the quantum to the MTU of the device (if any)
459 if (!m_quantum)
460 {
462 Ptr<NetDevice> dev;
463 // if the NetDeviceQueueInterface object is aggregated to a
464 // NetDevice, get the MTU of such NetDevice
465 if (ndqi && (dev = ndqi->GetObject<NetDevice>()))
466 {
467 m_quantum = dev->GetMtu();
468 NS_LOG_DEBUG("Setting the quantum to the MTU of the device: " << m_quantum);
469 }
470
471 if (!m_quantum)
472 {
473 NS_LOG_ERROR("The quantum parameter cannot be null");
474 return false;
475 }
476 }
477
479 {
480 NS_LOG_ERROR("The number of queues must be an integer multiple of the size "
481 "of the set of queues used by set associative hash");
482 return false;
483 }
484
485 // If UseL4S attribute is enabled then CE threshold must be set.
486 if (m_useL4s)
487 {
488 NS_ABORT_MSG_IF(m_ceThreshold == Time::Max(), "CE threshold not set");
489 if (!m_useEcn)
490 {
491 NS_LOG_WARN("Enabling ECN as L4S mode is enabled");
492 }
493 }
494 return true;
495}
496
497void
518
521{
522 NS_LOG_FUNCTION(this);
523
524 uint32_t maxBacklog = 0;
525 uint32_t index = 0;
527
528 /* Queue is full! Find the fat flow and drop packet(s) from it */
529 for (uint32_t i = 0; i < GetNQueueDiscClasses(); i++)
530 {
531 qd = GetQueueDiscClass(i)->GetQueueDisc();
532 uint32_t bytes = qd->GetNBytes();
533 if (bytes > maxBacklog)
534 {
535 maxBacklog = bytes;
536 index = i;
537 }
538 }
539
540 /* Our goal is to drop half of this fat flow backlog */
541 uint32_t len = 0;
542 uint32_t count = 0;
543 uint32_t threshold = maxBacklog >> 1;
544 qd = GetQueueDiscClass(index)->GetQueueDisc();
546
547 do
548 {
549 NS_LOG_DEBUG("Drop packet (overflow); count: " << count << " len: " << len
550 << " threshold: " << threshold);
551 item = qd->GetInternalQueue(0)->Dequeue();
553 len += item->GetSize();
554 } while (++count < m_dropBatchSize && len < threshold);
555
556 return index;
557}
558
559} // namespace ns3
AttributeValue implementation for Boolean.
Definition boolean.h:26
This class can be used to hold variables of floating point type such as 'double' or 'float'.
Definition double.h:31
A flow queue used by the FqPie queue disc.
void SetIndex(uint32_t index)
Set the index for this flow.
FlowStatus
Used to determine the status of this flow queue.
int32_t m_deficit
the deficit for this flow
void SetStatus(FlowStatus status)
Set the status for this flow.
static TypeId GetTypeId()
Get the type ID.
FlowStatus GetStatus() const
Get the status of this flow.
FlowStatus m_status
the status of this flow
uint32_t m_index
the index for this flow
void SetDeficit(uint32_t deficit)
Set the deficit for this flow.
uint32_t GetIndex() const
Get the index of this flow.
FqPieFlow()
FqPieFlow constructor.
void IncreaseDeficit(int32_t deficit)
Increase the deficit for this flow.
int32_t GetDeficit() const
Get the deficit for this flow.
A FqPie packet queue disc.
Time m_qDelayRef
Desired queue delay.
std::map< uint32_t, uint32_t > m_tags
Tags used by set associative hash.
bool m_useEcn
True if ECN is used (packets are marked instead of being dropped)
bool m_enableSetAssociativeHash
whether to enable set associative hash
uint32_t m_meanPktSize
Average packet size in bytes.
static constexpr const char * UNCLASSIFIED_DROP
No packet filter able to classify packet.
uint32_t GetQuantum() const
Get the quantum value.
uint32_t m_perturbation
hash perturbation value
FqPieQueueDisc()
FqPieQueueDisc constructor.
ObjectFactory m_queueDiscFactory
Factory to create a new queue.
bool DoEnqueue(Ptr< QueueDiscItem > item) override
This function actually enqueues a packet into the queue disc.
double m_a
Parameter to pie controller.
Time m_sUpdate
Start time of the update timer.
bool m_useDqRateEstimator
Enable/Disable usage of dequeue rate estimator for queue delay calculation.
Time m_ceThreshold
Threshold above which to CE mark.
uint32_t m_dqThreshold
Minimum queue size in bytes before dequeue rate is measured.
Ptr< QueueDiscItem > DoDequeue() override
This function actually extracts a packet from the queue disc.
bool CheckConfig() override
Check whether the current configuration is correct.
uint32_t m_dropBatchSize
Max number of packets dropped from the fat flow.
uint32_t m_quantum
Deficit assigned to flows at each round.
Time m_tUpdate
Time period after which CalculateP () is called.
uint32_t FqPieDrop()
Drop a packet from the head of the queue with the largest current byte count.
bool m_isCapDropAdjustment
Enable/Disable Cap Drop Adjustment feature mentioned in RFC 8033.
std::list< Ptr< FqPieFlow > > m_newFlows
The list of new flows.
Time m_maxBurst
Maximum burst allowed before random early dropping kicks in.
bool m_useDerandomization
Enable Derandomization feature mentioned in RFC 8033.
uint32_t m_setWays
size of a set of queues (used by set associative hash)
uint32_t m_flows
Number of flow queues.
static TypeId GetTypeId()
Get the type ID.
double m_markEcnTh
ECN marking threshold (default 10% as suggested in RFC 8033)
void InitializeParams() override
Initialize parameters (if any) before the first packet is enqueued.
std::map< uint32_t, uint32_t > m_flowsIndices
Map with the index of class for each flow.
uint32_t SetAssociativeHash(uint32_t flowHash)
Compute the index of the queue for the flow having the given flowHash, according to the set associati...
static constexpr const char * OVERLIMIT_DROP
Overlimit dropped packets.
bool m_useL4s
True if L4S is used (ECT1 packets are marked at CE threshold)
void SetQuantum(uint32_t quantum)
Set the quantum value.
double m_b
Parameter to pie controller.
ObjectFactory m_flowFactory
Factory to create a new flow.
std::list< Ptr< FqPieFlow > > m_oldFlows
The list of old flows.
Network layer to device interface.
Definition net-device.h:87
void SetAttribute(std::string name, const AttributeValue &value)
Set a single attribute, raising fatal errors if unsuccessful.
Ptr< Object > Create() const
Create an Object instance of the configured TypeId.
void Set(const std::string &name, const AttributeValue &value, Args &&... args)
Set an attribute to be set during construction.
void SetTypeId(TypeId tid)
Set the TypeId of the Objects to be created by this factory.
static const int PF_NO_MATCH
Standard value used by packet filters to indicate that no match was possible.
Implements PIE Active Queue Management discipline.
Smart pointer class similar to boost::intrusive_ptr.
QueueDiscClass is the base class for classes that are included in a queue disc.
Definition queue-disc.h:41
QueueDisc is an abstract base class providing the interface and implementing the operations common to...
Definition queue-disc.h:173
void AddQueueDiscClass(Ptr< QueueDiscClass > qdClass)
Add a queue disc class to the tail of the list of classes.
QueueSize GetCurrentSize() const
Get the current size of the queue disc in bytes, if operating in bytes mode, or packets,...
int32_t Classify(Ptr< QueueDiscItem > item)
Classify a packet by calling the packet filters, one at a time, until either a filter able to classif...
Ptr< NetDeviceQueueInterface > GetNetDeviceQueueInterface() const
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.
Ptr< QueueDiscClass > GetQueueDiscClass(std::size_t i) const
Get the i-th queue disc class.
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 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
AttributeValue implementation for QueueSize.
Definition queue-size.h:210
static Time Max()
Maximum representable Time Not to be confused with Max(Time,Time).
Definition nstime.h:286
AttributeValue implementation for Time.
Definition nstime.h:1395
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
Ptr< const AttributeChecker > MakeBooleanChecker()
Definition boolean.cc:113
Ptr< const AttributeAccessor > MakeBooleanAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method.
Definition boolean.h:70
Ptr< const AttributeChecker > MakeDoubleChecker()
Definition double.h:82
Ptr< const AttributeAccessor > MakeDoubleAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method.
Definition double.h:32
Ptr< const AttributeAccessor > MakeQueueSizeAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method.
Definition queue-size.h:210
Ptr< const AttributeChecker > MakeQueueSizeChecker()
Definition queue-size.cc:18
Ptr< const AttributeAccessor > MakeTimeAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method.
Definition nstime.h:1396
Ptr< const AttributeChecker > MakeTimeChecker()
Helper to make an unbounded Time checker.
Definition nstime.h:1416
Ptr< const AttributeChecker > MakeUintegerChecker()
Definition uinteger.h:85
Ptr< const AttributeAccessor > MakeUintegerAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method.
Definition uinteger.h:35
#define NS_ABORT_MSG_IF(cond, msg)
Abnormal program termination if a condition is true, with a message.
Definition abort.h:97
#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_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
#define NS_LOG_WARN(msg)
Use NS_LOG to output a message of level LOG_WARN.
Definition log.h:250
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition object-base.h:35
QueueSizeUnit
Enumeration of the operating modes of queues.
Definition queue-size.h:33
@ PACKETS
Use number of packets for queue size.
Definition queue-size.h:34
Time Seconds(double value)
Construct a Time in the indicated unit.
Definition nstime.h:1308
QueueDiscSizePolicy
Enumeration of the available policies to handle the queue disc size.
Definition queue-disc.h:96
@ MULTIPLE_QUEUES
Used by queue discs with multiple internal queues/child queue discs.
Definition queue-disc.h:99
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Ptr< T1 > StaticCast(const Ptr< T2 > &p)
Cast a Ptr.
Definition ptr.h:587