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 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License version 2 as
6 * published by the Free Software Foundation;
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16 *
17 * Authors: Pasquale Imputato <p.imputato@gmail.com>
18 * Stefano Avallone <stefano.avallone@unina.it>
19 */
20
21#include "fq-codel-queue-disc.h"
22
23#include "codel-queue-disc.h"
24
25#include "ns3/log.h"
26#include "ns3/net-device-queue-interface.h"
27#include "ns3/queue.h"
28#include "ns3/string.h"
29
30namespace ns3
31{
32
33NS_LOG_COMPONENT_DEFINE("FqCoDelQueueDisc");
34
36
37TypeId
39{
40 static TypeId tid = TypeId("ns3::FqCoDelFlow")
42 .SetGroupName("TrafficControl")
43 .AddConstructor<FqCoDelFlow>();
44 return tid;
45}
46
48 : m_deficit(0),
49 m_status(INACTIVE),
50 m_index(0)
51{
52 NS_LOG_FUNCTION(this);
53}
54
56{
57 NS_LOG_FUNCTION(this);
58}
59
60void
62{
63 NS_LOG_FUNCTION(this << deficit);
64 m_deficit = deficit;
65}
66
69{
70 NS_LOG_FUNCTION(this);
71 return m_deficit;
72}
73
74void
76{
77 NS_LOG_FUNCTION(this << deficit);
78 m_deficit += deficit;
79}
80
81void
83{
84 NS_LOG_FUNCTION(this);
85 m_status = status;
86}
87
90{
91 NS_LOG_FUNCTION(this);
92 return m_status;
93}
94
95void
97{
98 NS_LOG_FUNCTION(this);
99 m_index = index;
100}
101
104{
105 return m_index;
106}
107
109
110TypeId
112{
113 static TypeId tid =
114 TypeId("ns3::FqCoDelQueueDisc")
116 .SetGroupName("TrafficControl")
117 .AddConstructor<FqCoDelQueueDisc>()
118 .AddAttribute("UseEcn",
119 "True to use ECN (packets are marked instead of being dropped)",
120 BooleanValue(true),
123 .AddAttribute("Interval",
124 "The CoDel algorithm interval for each FQCoDel queue",
125 StringValue("100ms"),
128 .AddAttribute("Target",
129 "The CoDel algorithm target queue delay for each FQCoDel queue",
130 StringValue("5ms"),
133 .AddAttribute("MaxSize",
134 "The maximum number of packets accepted by this queue disc",
135 QueueSizeValue(QueueSize("10240p")),
136 MakeQueueSizeAccessor(&QueueDisc::SetMaxSize, &QueueDisc::GetMaxSize),
137 MakeQueueSizeChecker())
138 .AddAttribute("Flows",
139 "The number of queues into which the incoming packets are classified",
140 UintegerValue(1024),
142 MakeUintegerChecker<uint32_t>())
143 .AddAttribute("DropBatchSize",
144 "The maximum number of packets dropped from the fat flow",
145 UintegerValue(64),
147 MakeUintegerChecker<uint32_t>())
148 .AddAttribute("Perturbation",
149 "The salt used as an additional input to the hash function used to "
150 "classify packets",
151 UintegerValue(0),
153 MakeUintegerChecker<uint32_t>())
154 .AddAttribute("CeThreshold",
155 "The FqCoDel CE threshold for marking packets",
159 .AddAttribute("EnableSetAssociativeHash",
160 "Enable/Disable Set Associative Hash",
161 BooleanValue(false),
164 .AddAttribute("SetWays",
165 "The size of a set of queues (used by set associative hash)",
166 UintegerValue(8),
168 MakeUintegerChecker<uint32_t>())
169 .AddAttribute("UseL4s",
170 "True to use L4S (only ECT1 packets are marked at CE threshold)",
171 BooleanValue(false),
174 return tid;
175}
176
179 m_quantum(0)
180{
181 NS_LOG_FUNCTION(this);
182}
183
185{
186 NS_LOG_FUNCTION(this);
187}
188
189void
191{
192 NS_LOG_FUNCTION(this << quantum);
193 m_quantum = quantum;
194}
195
198{
199 return m_quantum;
200}
201
204{
205 NS_LOG_FUNCTION(this << flowHash);
206
207 uint32_t h = (flowHash % m_flows);
208 uint32_t innerHash = h % m_setWays;
209 uint32_t outerHash = h - innerHash;
210
211 for (uint32_t i = outerHash; i < outerHash + m_setWays; i++)
212 {
213 auto it = m_flowsIndices.find(i);
214
215 if (it == m_flowsIndices.end() ||
216 (m_tags.find(i) != m_tags.end() && m_tags[i] == flowHash) ||
217 StaticCast<FqCoDelFlow>(GetQueueDiscClass(it->second))->GetStatus() ==
219 {
220 // this queue has not been created yet or is associated with this flow
221 // or is inactive, hence we can use it
222 m_tags[i] = flowHash;
223 return i;
224 }
225 }
226
227 // all the queues of the set are used. Use the first queue of the set
228 m_tags[outerHash] = flowHash;
229 return outerHash;
230}
231
232bool
234{
235 NS_LOG_FUNCTION(this << item);
236
237 uint32_t flowHash;
238 uint32_t h;
239
240 if (GetNPacketFilters() == 0)
241 {
242 flowHash = item->Hash(m_perturbation);
243 }
244 else
245 {
246 int32_t ret = Classify(item);
247
248 if (ret != PacketFilter::PF_NO_MATCH)
249 {
250 flowHash = static_cast<uint32_t>(ret);
251 }
252 else
253 {
254 NS_LOG_ERROR("No filter has been able to classify this packet, drop it.");
256 return false;
257 }
258 }
259
261 {
262 h = SetAssociativeHash(flowHash);
263 }
264 else
265 {
266 h = flowHash % m_flows;
267 }
268
269 Ptr<FqCoDelFlow> flow;
270 if (m_flowsIndices.find(h) == m_flowsIndices.end())
271 {
272 NS_LOG_DEBUG("Creating a new flow queue with index " << h);
275 // If CoDel, Set values of CoDelQueueDisc to match this QueueDisc
276 Ptr<CoDelQueueDisc> codel = qd->GetObject<CoDelQueueDisc>();
277 if (codel)
278 {
279 codel->SetAttribute("UseEcn", BooleanValue(m_useEcn));
280 codel->SetAttribute("CeThreshold", TimeValue(m_ceThreshold));
281 codel->SetAttribute("UseL4s", BooleanValue(m_useL4s));
282 }
283 qd->Initialize();
284 flow->SetQueueDisc(qd);
285 flow->SetIndex(h);
286 AddQueueDiscClass(flow);
287
289 }
290 else
291 {
292 flow = StaticCast<FqCoDelFlow>(GetQueueDiscClass(m_flowsIndices[h]));
293 }
294
295 if (flow->GetStatus() == FqCoDelFlow::INACTIVE)
296 {
297 flow->SetStatus(FqCoDelFlow::NEW_FLOW);
298 flow->SetDeficit(m_quantum);
299 m_newFlows.push_back(flow);
300 }
301
302 flow->GetQueueDisc()->Enqueue(item);
303
304 NS_LOG_DEBUG("Packet enqueued into flow " << h << "; flow index " << m_flowsIndices[h]);
305
306 if (GetCurrentSize() > GetMaxSize())
307 {
308 NS_LOG_DEBUG("Overload; enter FqCodelDrop ()");
309 FqCoDelDrop();
310 }
311
312 return true;
313}
314
317{
318 NS_LOG_FUNCTION(this);
319
320 Ptr<FqCoDelFlow> flow;
322
323 do
324 {
325 bool found = false;
326
327 while (!found && !m_newFlows.empty())
328 {
329 flow = m_newFlows.front();
330
331 if (flow->GetDeficit() <= 0)
332 {
333 NS_LOG_DEBUG("Increase deficit for new flow index " << flow->GetIndex());
334 flow->IncreaseDeficit(m_quantum);
335 flow->SetStatus(FqCoDelFlow::OLD_FLOW);
336 m_oldFlows.splice(m_oldFlows.end(), m_newFlows, m_newFlows.begin());
337 }
338 else
339 {
340 NS_LOG_DEBUG("Found a new flow " << flow->GetIndex() << " with positive deficit");
341 found = true;
342 }
343 }
344
345 while (!found && !m_oldFlows.empty())
346 {
347 flow = m_oldFlows.front();
348
349 if (flow->GetDeficit() <= 0)
350 {
351 NS_LOG_DEBUG("Increase deficit for old flow index " << flow->GetIndex());
352 flow->IncreaseDeficit(m_quantum);
353 m_oldFlows.splice(m_oldFlows.end(), m_oldFlows, m_oldFlows.begin());
354 }
355 else
356 {
357 NS_LOG_DEBUG("Found an old flow " << flow->GetIndex() << " with positive deficit");
358 found = true;
359 }
360 }
361
362 if (!found)
363 {
364 NS_LOG_DEBUG("No flow found to dequeue a packet");
365 return nullptr;
366 }
367
368 item = flow->GetQueueDisc()->Dequeue();
369
370 if (!item)
371 {
372 NS_LOG_DEBUG("Could not get a packet from the selected flow queue");
373 if (!m_newFlows.empty())
374 {
375 flow->SetStatus(FqCoDelFlow::OLD_FLOW);
376 m_oldFlows.push_back(flow);
377 m_newFlows.pop_front();
378 }
379 else
380 {
381 flow->SetStatus(FqCoDelFlow::INACTIVE);
382 m_oldFlows.pop_front();
383 }
384 }
385 else
386 {
387 NS_LOG_DEBUG("Dequeued packet " << item->GetPacket());
388 }
389 } while (!item);
390
391 flow->IncreaseDeficit(item->GetSize() * -1);
392
393 return item;
394}
395
396bool
398{
399 NS_LOG_FUNCTION(this);
400 if (GetNQueueDiscClasses() > 0)
401 {
402 NS_LOG_ERROR("FqCoDelQueueDisc cannot have classes");
403 return false;
404 }
405
406 if (GetNInternalQueues() > 0)
407 {
408 NS_LOG_ERROR("FqCoDelQueueDisc cannot have internal queues");
409 return false;
410 }
411
412 // we are at initialization time. If the user has not set a quantum value,
413 // set the quantum to the MTU of the device (if any)
414 if (!m_quantum)
415 {
417 Ptr<NetDevice> dev;
418 // if the NetDeviceQueueInterface object is aggregated to a
419 // NetDevice, get the MTU of such NetDevice
420 if (ndqi && (dev = ndqi->GetObject<NetDevice>()))
421 {
422 m_quantum = dev->GetMtu();
423 NS_LOG_DEBUG("Setting the quantum to the MTU of the device: " << m_quantum);
424 }
425
426 if (!m_quantum)
427 {
428 NS_LOG_ERROR("The quantum parameter cannot be null");
429 return false;
430 }
431 }
432
434 {
435 NS_LOG_ERROR("The number of queues must be an integer multiple of the size "
436 "of the set of queues used by set associative hash");
437 return false;
438 }
439
440 if (m_useL4s)
441 {
442 NS_ABORT_MSG_IF(m_ceThreshold == Time::Max(), "CE threshold not set");
443 if (!m_useEcn)
444 {
445 NS_LOG_WARN("Enabling ECN as L4S mode is enabled");
446 }
447 }
448 return true;
449}
450
451void
453{
454 NS_LOG_FUNCTION(this);
455
456 m_flowFactory.SetTypeId("ns3::FqCoDelFlow");
457
458 m_queueDiscFactory.SetTypeId("ns3::CoDelQueueDisc");
462}
463
466{
467 NS_LOG_FUNCTION(this);
468
469 uint32_t maxBacklog = 0;
470 uint32_t index = 0;
472
473 /* Queue is full! Find the fat flow and drop packet(s) from it */
474 for (uint32_t i = 0; i < GetNQueueDiscClasses(); i++)
475 {
476 qd = GetQueueDiscClass(i)->GetQueueDisc();
477 uint32_t bytes = qd->GetNBytes();
478 if (bytes > maxBacklog)
479 {
480 maxBacklog = bytes;
481 index = i;
482 }
483 }
484
485 /* Our goal is to drop half of this fat flow backlog */
486 uint32_t len = 0;
487 uint32_t count = 0;
488 uint32_t threshold = maxBacklog >> 1;
489 qd = GetQueueDiscClass(index)->GetQueueDisc();
491
492 do
493 {
494 NS_LOG_DEBUG("Drop packet (overflow); count: " << count << " len: " << len
495 << " threshold: " << threshold);
496 item = qd->GetInternalQueue(0)->Dequeue();
498 len += item->GetSize();
499 } while (++count < m_dropBatchSize && len < threshold);
500
501 return index;
502}
503
504} // namespace ns3
AttributeValue implementation for Boolean.
Definition: boolean.h:37
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:98
void SetAttribute(std::string name, const AttributeValue &value)
Set a single attribute, raising fatal errors if unsuccessful.
Definition: object-base.cc:200
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.
Definition: packet-filter.h:49
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:78
QueueDiscClass is the base class for classes that are included in a queue disc.
Definition: queue-disc.h:52
QueueDisc is an abstract base class providing the interface and implementing the operations common to...
Definition: queue-disc.h:184
void AddQueueDiscClass(Ptr< QueueDiscClass > qdClass)
Add a queue disc class to the tail of the list of classes.
Definition: queue-disc.cc:628
QueueSize GetCurrentSize()
Get the current size of the queue disc in bytes, if operating in bytes mode, or packets,...
Definition: queue-disc.cc:519
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...
Definition: queue-disc.cc:671
Ptr< NetDeviceQueueInterface > GetNetDeviceQueueInterface() const
Definition: queue-disc.cc:542
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 GetNQueueDiscClasses() const
Get the number of queue disc classes.
Definition: queue-disc.cc:665
QueueSize GetMaxSize() const
Get the maximum size of the queue disc.
Definition: queue-disc.cc:450
Ptr< QueueDiscClass > GetQueueDiscClass(std::size_t i) const
Get the i-th queue disc class.
Definition: queue-disc.cc:658
std::size_t GetNPacketFilters() const
Get the number of packet filters.
Definition: queue-disc.cc:622
bool SetMaxSize(QueueSize size)
Set the maximum size of the queue disc.
Definition: queue-disc.cc:478
std::size_t GetNInternalQueues() const
Get the number of internal queues.
Definition: queue-disc.cc:602
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:726
Class for representing queue sizes.
Definition: queue-size.h:96
AttributeValue implementation for QueueSize.
Hold variables of type string.
Definition: string.h:56
static Time Max()
Maximum representable Time Not to be confused with Max(Time,Time).
Definition: nstime.h:296
AttributeValue implementation for Time.
Definition: nstime.h:1423
a unique identifier for an interface.
Definition: type-id.h:59
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:936
Hold an unsigned integer type.
Definition: uinteger.h:45
Ptr< const AttributeAccessor > MakeBooleanAccessor(T1 a1)
Definition: boolean.h:86
Ptr< const AttributeChecker > MakeBooleanChecker()
Definition: boolean.cc:124
Ptr< const AttributeChecker > MakeStringChecker()
Definition: string.cc:30
Ptr< const AttributeAccessor > MakeStringAccessor(T1 a1)
Definition: string.h:57
Ptr< const AttributeChecker > MakeTimeChecker()
Helper to make an unbounded Time checker.
Definition: nstime.h:1444
Ptr< const AttributeAccessor > MakeTimeAccessor(T1 a1)
Definition: nstime.h:1424
Ptr< const AttributeAccessor > MakeUintegerAccessor(T1 a1)
Definition: uinteger.h:46
#define NS_ABORT_MSG_IF(cond, msg)
Abnormal program termination if a condition is true, with a message.
Definition: abort.h:108
#define NS_LOG_ERROR(msg)
Use NS_LOG to output a message of level LOG_ERROR.
Definition: log.h:254
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:202
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:268
#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:261
@ INACTIVE
Inactive Period or unslotted CSMA-CA.
Definition: lr-wpan-mac.h:96
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:46
QueueSizeUnit
Enumeration of the operating modes of queues.
Definition: queue-size.h:44
@ PACKETS
Use number of packets for queue size.
Definition: queue-size.h:45
QueueDiscSizePolicy
Enumeration of the available policies to handle the queue disc size.
Definition: queue-disc.h:107
@ MULTIPLE_QUEUES
Used by queue discs with multiple internal queues/child queue discs.
Definition: queue-disc.h:110
Every class exported by the ns3 library is enclosed in the ns3 namespace.