A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
fq-codel-queue-disc.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2016 Universita' degli Studi di Napoli Federico II
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Authors: Pasquale Imputato <p.imputato@gmail.com>
7 * Stefano Avallone <stefano.avallone@unina.it>
8 */
9
10#include "fq-codel-queue-disc.h"
11
12#include "codel-queue-disc.h"
13
14#include "ns3/log.h"
15#include "ns3/net-device-queue-interface.h"
16#include "ns3/queue.h"
17#include "ns3/string.h"
18
19namespace ns3
20{
21
22NS_LOG_COMPONENT_DEFINE("FqCoDelQueueDisc");
23
25
26TypeId
28{
29 static TypeId tid = TypeId("ns3::FqCoDelFlow")
31 .SetGroupName("TrafficControl")
32 .AddConstructor<FqCoDelFlow>();
33 return tid;
34}
35
37 : m_deficit(0),
38 m_status(INACTIVE),
39 m_index(0)
40{
41 NS_LOG_FUNCTION(this);
42}
43
48
49void
51{
52 NS_LOG_FUNCTION(this << deficit);
53 m_deficit = deficit;
54}
55
58{
59 NS_LOG_FUNCTION(this);
60 return m_deficit;
61}
62
63void
65{
66 NS_LOG_FUNCTION(this << deficit);
67 m_deficit += deficit;
68}
69
70void
72{
73 NS_LOG_FUNCTION(this);
74 m_status = status;
75}
76
79{
80 NS_LOG_FUNCTION(this);
81 return m_status;
82}
83
84void
86{
87 NS_LOG_FUNCTION(this);
88 m_index = index;
89}
90
93{
94 return m_index;
95}
96
98
101{
102 static TypeId tid =
103 TypeId("ns3::FqCoDelQueueDisc")
105 .SetGroupName("TrafficControl")
106 .AddConstructor<FqCoDelQueueDisc>()
107 .AddAttribute("UseEcn",
108 "True to use ECN (packets are marked instead of being dropped)",
109 BooleanValue(true),
112 .AddAttribute("Interval",
113 "The CoDel algorithm interval for each FQCoDel queue",
114 StringValue("100ms"),
117 .AddAttribute("Target",
118 "The CoDel algorithm target queue delay for each FQCoDel queue",
119 StringValue("5ms"),
122 .AddAttribute("MaxSize",
123 "The maximum number of packets accepted by this queue disc",
124 QueueSizeValue(QueueSize("10240p")),
127 .AddAttribute("Flows",
128 "The number of queues into which the incoming packets are classified",
129 UintegerValue(1024),
132 .AddAttribute("DropBatchSize",
133 "The maximum number of packets dropped from the fat flow",
134 UintegerValue(64),
137 .AddAttribute("Perturbation",
138 "The salt used as an additional input to the hash function used to "
139 "classify packets",
140 UintegerValue(0),
143 .AddAttribute("CeThreshold",
144 "The FqCoDel CE threshold for marking packets",
148 .AddAttribute("EnableSetAssociativeHash",
149 "Enable/Disable Set Associative Hash",
150 BooleanValue(false),
153 .AddAttribute("SetWays",
154 "The size of a set of queues (used by set associative hash)",
155 UintegerValue(8),
158 .AddAttribute("UseL4s",
159 "True to use L4S (only ECT1 packets are marked at CE threshold)",
160 BooleanValue(false),
163 return tid;
164}
165
172
177
178void
180{
181 NS_LOG_FUNCTION(this << quantum);
182 m_quantum = quantum;
183}
184
187{
188 return m_quantum;
189}
190
193{
194 NS_LOG_FUNCTION(this << flowHash);
195
196 uint32_t h = (flowHash % m_flows);
197 uint32_t innerHash = h % m_setWays;
198 uint32_t outerHash = h - innerHash;
199
200 for (uint32_t i = outerHash; i < outerHash + m_setWays; i++)
201 {
202 auto it = m_flowsIndices.find(i);
203
204 if (it == m_flowsIndices.end() ||
205 (m_tags.find(i) != m_tags.end() && m_tags[i] == flowHash) ||
206 StaticCast<FqCoDelFlow>(GetQueueDiscClass(it->second))->GetStatus() ==
208 {
209 // this queue has not been created yet or is associated with this flow
210 // or is inactive, hence we can use it
211 m_tags[i] = flowHash;
212 return i;
213 }
214 }
215
216 // all the queues of the set are used. Use the first queue of the set
217 m_tags[outerHash] = flowHash;
218 return outerHash;
219}
220
221bool
223{
224 NS_LOG_FUNCTION(this << item);
225
226 uint32_t flowHash;
227 uint32_t h;
228
229 if (GetNPacketFilters() == 0)
230 {
231 flowHash = item->Hash(m_perturbation);
232 }
233 else
234 {
235 int32_t ret = Classify(item);
236
237 if (ret != PacketFilter::PF_NO_MATCH)
238 {
239 flowHash = static_cast<uint32_t>(ret);
240 }
241 else
242 {
243 NS_LOG_ERROR("No filter has been able to classify this packet, drop it.");
245 return false;
246 }
247 }
248
250 {
251 h = SetAssociativeHash(flowHash);
252 }
253 else
254 {
255 h = flowHash % m_flows;
256 }
257
258 Ptr<FqCoDelFlow> flow;
259 if (m_flowsIndices.find(h) == m_flowsIndices.end())
260 {
261 NS_LOG_DEBUG("Creating a new flow queue with index " << h);
264 // If CoDel, Set values of CoDelQueueDisc to match this QueueDisc
265 Ptr<CoDelQueueDisc> codel = qd->GetObject<CoDelQueueDisc>();
266 if (codel)
267 {
268 codel->SetAttribute("UseEcn", BooleanValue(m_useEcn));
269 codel->SetAttribute("CeThreshold", TimeValue(m_ceThreshold));
270 codel->SetAttribute("UseL4s", BooleanValue(m_useL4s));
271 }
272 qd->Initialize();
273 flow->SetQueueDisc(qd);
274 flow->SetIndex(h);
275 AddQueueDiscClass(flow);
276
278 }
279 else
280 {
282 }
283
284 if (flow->GetStatus() == FqCoDelFlow::INACTIVE)
285 {
286 flow->SetStatus(FqCoDelFlow::NEW_FLOW);
287 flow->SetDeficit(m_quantum);
288 m_newFlows.push_back(flow);
289 }
290
291 flow->GetQueueDisc()->Enqueue(item);
292
293 NS_LOG_DEBUG("Packet enqueued into flow " << h << "; flow index " << m_flowsIndices[h]);
294
295 if (GetCurrentSize() > GetMaxSize())
296 {
297 NS_LOG_DEBUG("Overload; enter FqCodelDrop ()");
298 FqCoDelDrop();
299 }
300
301 return true;
302}
303
306{
307 NS_LOG_FUNCTION(this);
308
309 Ptr<FqCoDelFlow> flow;
311
312 do
313 {
314 bool found = false;
315
316 while (!found && !m_newFlows.empty())
317 {
318 flow = m_newFlows.front();
319
320 if (flow->GetDeficit() <= 0)
321 {
322 NS_LOG_DEBUG("Increase deficit for new flow index " << flow->GetIndex());
323 flow->IncreaseDeficit(m_quantum);
324 flow->SetStatus(FqCoDelFlow::OLD_FLOW);
325 m_oldFlows.splice(m_oldFlows.end(), m_newFlows, m_newFlows.begin());
326 }
327 else
328 {
329 NS_LOG_DEBUG("Found a new flow " << flow->GetIndex() << " with positive deficit");
330 found = true;
331 }
332 }
333
334 while (!found && !m_oldFlows.empty())
335 {
336 flow = m_oldFlows.front();
337
338 if (flow->GetDeficit() <= 0)
339 {
340 NS_LOG_DEBUG("Increase deficit for old flow index " << flow->GetIndex());
341 flow->IncreaseDeficit(m_quantum);
342 m_oldFlows.splice(m_oldFlows.end(), m_oldFlows, m_oldFlows.begin());
343 }
344 else
345 {
346 NS_LOG_DEBUG("Found an old flow " << flow->GetIndex() << " with positive deficit");
347 found = true;
348 }
349 }
350
351 if (!found)
352 {
353 NS_LOG_DEBUG("No flow found to dequeue a packet");
354 return nullptr;
355 }
356
357 item = flow->GetQueueDisc()->Dequeue();
358
359 if (!item)
360 {
361 NS_LOG_DEBUG("Could not get a packet from the selected flow queue");
362 if (!m_newFlows.empty())
363 {
364 flow->SetStatus(FqCoDelFlow::OLD_FLOW);
365 m_oldFlows.push_back(flow);
366 m_newFlows.pop_front();
367 }
368 else
369 {
370 flow->SetStatus(FqCoDelFlow::INACTIVE);
371 m_oldFlows.pop_front();
372 }
373 }
374 else
375 {
376 NS_LOG_DEBUG("Dequeued packet " << item->GetPacket());
377 }
378 } while (!item);
379
380 flow->IncreaseDeficit(item->GetSize() * -1);
381
382 return item;
383}
384
385bool
387{
388 NS_LOG_FUNCTION(this);
389 if (GetNQueueDiscClasses() > 0)
390 {
391 NS_LOG_ERROR("FqCoDelQueueDisc cannot have classes");
392 return false;
393 }
394
395 if (GetNInternalQueues() > 0)
396 {
397 NS_LOG_ERROR("FqCoDelQueueDisc cannot have internal queues");
398 return false;
399 }
400
401 // we are at initialization time. If the user has not set a quantum value,
402 // set the quantum to the MTU of the device (if any)
403 if (!m_quantum)
404 {
406 Ptr<NetDevice> dev;
407 // if the NetDeviceQueueInterface object is aggregated to a
408 // NetDevice, get the MTU of such NetDevice
409 if (ndqi && (dev = ndqi->GetObject<NetDevice>()))
410 {
411 m_quantum = dev->GetMtu();
412 NS_LOG_DEBUG("Setting the quantum to the MTU of the device: " << m_quantum);
413 }
414
415 if (!m_quantum)
416 {
417 NS_LOG_ERROR("The quantum parameter cannot be null");
418 return false;
419 }
420 }
421
423 {
424 NS_LOG_ERROR("The number of queues must be an integer multiple of the size "
425 "of the set of queues used by set associative hash");
426 return false;
427 }
428
429 if (m_useL4s)
430 {
431 NS_ABORT_MSG_IF(m_ceThreshold == Time::Max(), "CE threshold not set");
432 if (!m_useEcn)
433 {
434 NS_LOG_WARN("Enabling ECN as L4S mode is enabled");
435 }
436 }
437 return true;
438}
439
440void
442{
443 NS_LOG_FUNCTION(this);
444
445 m_flowFactory.SetTypeId("ns3::FqCoDelFlow");
446
447 m_queueDiscFactory.SetTypeId("ns3::CoDelQueueDisc");
451}
452
455{
456 NS_LOG_FUNCTION(this);
457
458 uint32_t maxBacklog = 0;
459 uint32_t index = 0;
461
462 /* Queue is full! Find the fat flow and drop packet(s) from it */
463 for (uint32_t i = 0; i < GetNQueueDiscClasses(); i++)
464 {
465 qd = GetQueueDiscClass(i)->GetQueueDisc();
466 uint32_t bytes = qd->GetNBytes();
467 if (bytes > maxBacklog)
468 {
469 maxBacklog = bytes;
470 index = i;
471 }
472 }
473
474 /* Our goal is to drop half of this fat flow backlog */
475 uint32_t len = 0;
476 uint32_t count = 0;
477 uint32_t threshold = maxBacklog >> 1;
478 qd = GetQueueDiscClass(index)->GetQueueDisc();
480
481 do
482 {
483 NS_LOG_DEBUG("Drop packet (overflow); count: " << count << " len: " << len
484 << " threshold: " << threshold);
485 item = qd->GetInternalQueue(0)->Dequeue();
487 len += item->GetSize();
488 } while (++count < m_dropBatchSize && len < threshold);
489
490 return index;
491}
492
493} // namespace ns3
A CoDel packet queue disc.
A flow queue used by the FqCoDel queue disc.
FqCoDelFlow()
FqCoDelFlow constructor.
FlowStatus GetStatus() const
Get the status of this flow.
void SetIndex(uint32_t index)
Set the index for this flow.
uint32_t GetIndex() const
Get the index of this flow.
static TypeId GetTypeId()
Get the type ID.
void SetDeficit(uint32_t deficit)
Set the deficit for this flow.
int32_t m_deficit
the deficit for this flow
FlowStatus m_status
the status of this flow
int32_t GetDeficit() const
Get the deficit for this flow.
uint32_t m_index
the index for this flow
void IncreaseDeficit(int32_t deficit)
Increase the deficit for this flow.
void SetStatus(FlowStatus status)
Set the status for this flow.
FlowStatus
Used to determine the status of this flow queue.
A FqCoDel packet queue disc.
std::list< Ptr< FqCoDelFlow > > m_oldFlows
The list of old flows.
Time m_ceThreshold
Threshold above which to CE mark.
uint32_t m_setWays
size of a set of queues (used by set associative hash)
void InitializeParams() override
Initialize parameters (if any) before the first packet is enqueued.
ObjectFactory m_queueDiscFactory
Factory to create a new queue.
static constexpr const char * UNCLASSIFIED_DROP
No packet filter able to classify packet.
static constexpr const char * OVERLIMIT_DROP
Overlimit dropped packets.
ObjectFactory m_flowFactory
Factory to create a new flow.
uint32_t FqCoDelDrop()
Drop a packet from the head of the queue with the largest current byte count.
Ptr< QueueDiscItem > DoDequeue() override
This function actually extracts a packet from the queue disc.
void SetQuantum(uint32_t quantum)
Set the quantum value.
std::string m_interval
CoDel interval attribute.
uint32_t m_dropBatchSize
Max number of packets dropped from the fat flow.
bool DoEnqueue(Ptr< QueueDiscItem > item) override
This function actually enqueues a packet into the queue disc.
std::string m_target
CoDel target attribute.
bool m_useEcn
True if ECN is used (packets are marked instead of being dropped)
FqCoDelQueueDisc()
FqCoDelQueueDisc constructor.
uint32_t m_perturbation
hash perturbation value
std::map< uint32_t, uint32_t > m_flowsIndices
Map with the index of class for each flow.
std::map< uint32_t, uint32_t > m_tags
Tags used by set associative hash.
bool CheckConfig() override
Check whether the current configuration is correct.
uint32_t SetAssociativeHash(uint32_t flowHash)
Compute the index of the queue for the flow having the given flowHash, according to the set associati...
bool m_useL4s
True if L4S is used (ECT1 packets are marked at CE threshold)
bool m_enableSetAssociativeHash
whether to enable set associative hash
uint32_t m_quantum
Deficit assigned to flows at each round.
std::list< Ptr< FqCoDelFlow > > m_newFlows
The list of new flows.
static TypeId GetTypeId()
Get the type ID.
uint32_t m_flows
Number of flow queues.
uint32_t GetQuantum() const
Get the quantum value.
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.
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
Hold variables of type string.
Definition string.h:45
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_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
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< 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 > MakeQueueSizeChecker()
Definition queue-size.cc:18
Ptr< T1 > StaticCast(const Ptr< T2 > &p)
Cast a Ptr.
Definition ptr.h:587
Ptr< const AttributeChecker > MakeStringChecker()
Definition string.cc:19
Ptr< const AttributeAccessor > MakeStringAccessor(T1 a1)
Definition string.h:46
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