A Discrete-Event Network Simulator
API
fq-codel-queue-disc.cc
Go to the documentation of this file.
1/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/*
3 * Copyright (c) 2016 Universita' degli Studi di Napoli Federico II
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation;
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 *
18 * Authors: Pasquale Imputato <p.imputato@gmail.com>
19 * Stefano Avallone <stefano.avallone@unina.it>
20*/
21
22#include "ns3/log.h"
23#include "ns3/string.h"
24#include "ns3/queue.h"
25#include "fq-codel-queue-disc.h"
26#include "codel-queue-disc.h"
27#include "ns3/net-device-queue-interface.h"
28
29namespace ns3 {
30
31NS_LOG_COMPONENT_DEFINE ("FqCoDelQueueDisc");
32
33NS_OBJECT_ENSURE_REGISTERED (FqCoDelFlow);
34
36{
37 static TypeId tid = TypeId ("ns3::FqCoDelFlow")
39 .SetGroupName ("TrafficControl")
40 .AddConstructor<FqCoDelFlow> ()
41 ;
42 return tid;
43}
44
46 : m_deficit (0),
47 m_status (INACTIVE),
48 m_index (0)
49{
50 NS_LOG_FUNCTION (this);
51}
52
54{
55 NS_LOG_FUNCTION (this);
56}
57
58void
60{
61 NS_LOG_FUNCTION (this << deficit);
62 m_deficit = deficit;
63}
64
67{
68 NS_LOG_FUNCTION (this);
69 return m_deficit;
70}
71
72void
74{
75 NS_LOG_FUNCTION (this << deficit);
76 m_deficit += deficit;
77}
78
79void
81{
82 NS_LOG_FUNCTION (this);
83 m_status = status;
84}
85
88{
89 NS_LOG_FUNCTION (this);
90 return m_status;
91}
92
93void
95{
96 NS_LOG_FUNCTION (this);
97 m_index = index;
98}
99
102{
103 return m_index;
104}
105
106
108
110{
111 static TypeId tid = TypeId ("ns3::FqCoDelQueueDisc")
113 .SetGroupName ("TrafficControl")
114 .AddConstructor<FqCoDelQueueDisc> ()
115 .AddAttribute ("UseEcn",
116 "True to use ECN (packets are marked instead of being dropped)",
117 BooleanValue (true),
120 .AddAttribute ("Interval",
121 "The CoDel algorithm interval for each FQCoDel queue",
122 StringValue ("100ms"),
125 .AddAttribute ("Target",
126 "The CoDel algorithm target queue delay for each FQCoDel queue",
127 StringValue ("5ms"),
130 .AddAttribute ("MaxSize",
131 "The maximum number of packets accepted by this queue disc",
132 QueueSizeValue (QueueSize ("10240p")),
133 MakeQueueSizeAccessor (&QueueDisc::SetMaxSize,
135 MakeQueueSizeChecker ())
136 .AddAttribute ("Flows",
137 "The number of queues into which the incoming packets are classified",
138 UintegerValue (1024),
140 MakeUintegerChecker<uint32_t> ())
141 .AddAttribute ("DropBatchSize",
142 "The maximum number of packets dropped from the fat flow",
143 UintegerValue (64),
145 MakeUintegerChecker<uint32_t> ())
146 .AddAttribute ("Perturbation",
147 "The salt used as an additional input to the hash function used to classify packets",
148 UintegerValue (0),
150 MakeUintegerChecker<uint32_t> ())
151 .AddAttribute ("CeThreshold",
152 "The FqCoDel CE threshold for marking packets",
153 TimeValue (Time::Max ()),
156 .AddAttribute ("EnableSetAssociativeHash",
157 "Enable/Disable Set Associative Hash",
158 BooleanValue (false),
161 .AddAttribute ("SetWays",
162 "The size of a set of queues (used by set associative hash)",
163 UintegerValue (8),
165 MakeUintegerChecker<uint32_t> ())
166 .AddAttribute ("UseL4s",
167 "True to use L4S (only ECT1 packets are marked at CE threshold)",
168 BooleanValue (false),
171 ;
172 return tid;
173}
174
177 m_quantum (0)
178{
179 NS_LOG_FUNCTION (this);
180}
181
183{
184 NS_LOG_FUNCTION (this);
185}
186
187void
189{
190 NS_LOG_FUNCTION (this << quantum);
191 m_quantum = quantum;
192}
193
196{
197 return m_quantum;
198}
199
202{
203 NS_LOG_FUNCTION (this << flowHash);
204
205 uint32_t h = (flowHash % m_flows);
206 uint32_t innerHash = h % m_setWays;
207 uint32_t outerHash = h - innerHash;
208
209 for (uint32_t i = outerHash; i < outerHash + m_setWays; i++)
210 {
211 auto it = m_flowsIndices.find (i);
212
213 if (it == m_flowsIndices.end ()
214 || (m_tags.find (i) != m_tags.end () && m_tags[i] == flowHash)
215 || StaticCast<FqCoDelFlow> (GetQueueDiscClass (it->second))->GetStatus () == FqCoDelFlow::INACTIVE)
216 {
217 // this queue has not been created yet or is associated with this flow
218 // or is inactive, hence we can use it
219 m_tags[i] = flowHash;
220 return i;
221 }
222 }
223
224 // all the queues of the set are used. Use the first queue of the set
225 m_tags[outerHash] = flowHash;
226 return outerHash;
227}
228
229bool
231{
232 NS_LOG_FUNCTION (this << item);
233
234 uint32_t flowHash, h;
235
236 if (GetNPacketFilters () == 0)
237 {
238 flowHash = item->Hash (m_perturbation);
239 }
240 else
241 {
242 int32_t ret = Classify (item);
243
244 if (ret != PacketFilter::PF_NO_MATCH)
245 {
246 flowHash = static_cast<uint32_t> (ret);
247 }
248 else
249 {
250 NS_LOG_ERROR ("No filter has been able to classify this packet, drop it.");
252 return false;
253 }
254 }
255
257 {
258 h = SetAssociativeHash (flowHash);
259 }
260 else
261 {
262 h = flowHash % m_flows;
263 }
264
265 Ptr<FqCoDelFlow> flow;
266 if (m_flowsIndices.find (h) == m_flowsIndices.end ())
267 {
268 NS_LOG_DEBUG ("Creating a new flow queue with index " << h);
271 // If CoDel, Set values of CoDelQueueDisc to match this QueueDisc
272 Ptr<CoDelQueueDisc> codel = qd->GetObject<CoDelQueueDisc> ();
273 if (codel)
274 {
275 codel->SetAttribute ("UseEcn", BooleanValue (m_useEcn));
276 codel->SetAttribute ("CeThreshold", TimeValue (m_ceThreshold));
277 codel->SetAttribute ("UseL4s", BooleanValue (m_useL4s));
278 }
279 qd->Initialize ();
280 flow->SetQueueDisc (qd);
281 flow->SetIndex (h);
282 AddQueueDiscClass (flow);
283
285 }
286 else
287 {
288 flow = StaticCast<FqCoDelFlow> (GetQueueDiscClass (m_flowsIndices[h]));
289 }
290
291 if (flow->GetStatus () == FqCoDelFlow::INACTIVE)
292 {
293 flow->SetStatus (FqCoDelFlow::NEW_FLOW);
294 flow->SetDeficit (m_quantum);
295 m_newFlows.push_back (flow);
296 }
297
298 flow->GetQueueDisc ()->Enqueue (item);
299
300 NS_LOG_DEBUG ("Packet enqueued into flow " << h << "; flow index " << m_flowsIndices[h]);
301
302 if (GetCurrentSize () > GetMaxSize ())
303 {
304 NS_LOG_DEBUG ("Overload; enter FqCodelDrop ()");
305 FqCoDelDrop ();
306 }
307
308 return true;
309}
310
313{
314 NS_LOG_FUNCTION (this);
315
316 Ptr<FqCoDelFlow> flow;
318
319 do
320 {
321 bool found = false;
322
323 while (!found && !m_newFlows.empty ())
324 {
325 flow = m_newFlows.front ();
326
327 if (flow->GetDeficit () <= 0)
328 {
329 NS_LOG_DEBUG ("Increase deficit for new flow index " << flow->GetIndex ());
330 flow->IncreaseDeficit (m_quantum);
331 flow->SetStatus (FqCoDelFlow::OLD_FLOW);
332 m_oldFlows.splice (m_oldFlows.end (), m_newFlows, m_newFlows.begin ());
333 }
334 else
335 {
336 NS_LOG_DEBUG ("Found a new flow " << flow->GetIndex () << " with positive deficit");
337 found = true;
338 }
339 }
340
341 while (!found && !m_oldFlows.empty ())
342 {
343 flow = m_oldFlows.front ();
344
345 if (flow->GetDeficit () <= 0)
346 {
347 NS_LOG_DEBUG ("Increase deficit for old flow index " << flow->GetIndex ());
348 flow->IncreaseDeficit (m_quantum);
349 m_oldFlows.splice (m_oldFlows.end (), m_oldFlows, m_oldFlows.begin ());
350 }
351 else
352 {
353 NS_LOG_DEBUG ("Found an old flow " << flow->GetIndex () << " with positive deficit");
354 found = true;
355 }
356 }
357
358 if (!found)
359 {
360 NS_LOG_DEBUG ("No flow found to dequeue a packet");
361 return 0;
362 }
363
364 item = flow->GetQueueDisc ()->Dequeue ();
365
366 if (!item)
367 {
368 NS_LOG_DEBUG ("Could not get a packet from the selected flow queue");
369 if (!m_newFlows.empty ())
370 {
371 flow->SetStatus (FqCoDelFlow::OLD_FLOW);
372 m_oldFlows.push_back (flow);
373 m_newFlows.pop_front ();
374 }
375 else
376 {
377 flow->SetStatus (FqCoDelFlow::INACTIVE);
378 m_oldFlows.pop_front ();
379 }
380 }
381 else
382 {
383 NS_LOG_DEBUG ("Dequeued packet " << item->GetPacket ());
384 }
385 } while (item == 0);
386
387 flow->IncreaseDeficit (item->GetSize () * -1);
388
389 return item;
390}
391
392bool
394{
395 NS_LOG_FUNCTION (this);
396 if (GetNQueueDiscClasses () > 0)
397 {
398 NS_LOG_ERROR ("FqCoDelQueueDisc cannot have classes");
399 return false;
400 }
401
402 if (GetNInternalQueues () > 0)
403 {
404 NS_LOG_ERROR ("FqCoDelQueueDisc cannot have internal queues");
405 return false;
406 }
407
408 // we are at initialization time. If the user has not set a quantum value,
409 // set the quantum to the MTU of the device (if any)
410 if (!m_quantum)
411 {
413 Ptr<NetDevice> dev;
414 // if the NetDeviceQueueInterface object is aggregated to a
415 // NetDevice, get the MTU of such NetDevice
416 if (ndqi && (dev = ndqi->GetObject<NetDevice> ()))
417 {
418 m_quantum = dev->GetMtu ();
419 NS_LOG_DEBUG ("Setting the quantum to the MTU of the device: " << m_quantum);
420 }
421
422 if (!m_quantum)
423 {
424 NS_LOG_ERROR ("The quantum parameter cannot be null");
425 return false;
426 }
427 }
428
430 {
431 NS_LOG_ERROR ("The number of queues must be an integer multiple of the size "
432 "of the set of queues used by set associative hash");
433 return false;
434 }
435
436 if (m_useL4s)
437 {
438 NS_ABORT_MSG_IF (m_ceThreshold == Time::Max(), "CE threshold not set");
439 if (m_useEcn == false)
440 {
441 NS_LOG_WARN ("Enabling ECN as L4S mode is enabled");
442 }
443 }
444 return true;
445}
446
447void
449{
450 NS_LOG_FUNCTION (this);
451
452 m_flowFactory.SetTypeId ("ns3::FqCoDelFlow");
453
454 m_queueDiscFactory.SetTypeId ("ns3::CoDelQueueDisc");
458}
459
462{
463 NS_LOG_FUNCTION (this);
464
465 uint32_t maxBacklog = 0, index = 0;
467
468 /* Queue is full! Find the fat flow and drop packet(s) from it */
469 for (uint32_t i = 0; i < GetNQueueDiscClasses (); i++)
470 {
471 qd = GetQueueDiscClass (i)->GetQueueDisc ();
472 uint32_t bytes = qd->GetNBytes ();
473 if (bytes > maxBacklog)
474 {
475 maxBacklog = bytes;
476 index = i;
477 }
478 }
479
480 /* Our goal is to drop half of this fat flow backlog */
481 uint32_t len = 0, count = 0, threshold = maxBacklog >> 1;
482 qd = GetQueueDiscClass (index)->GetQueueDisc ();
484
485 do
486 {
487 NS_LOG_DEBUG ("Drop packet (overflow); count: " << count << " len: " << len << " threshold: " << threshold);
488 item = qd->GetInternalQueue (0)->Dequeue ();
490 len += item->GetSize ();
491 } while (++count < m_dropBatchSize && len < threshold);
492
493 return index;
494}
495
496} // namespace ns3
497
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.
static TypeId GetTypeId(void)
Get the type ID.
void SetIndex(uint32_t index)
Set the index for this flow.
int32_t GetDeficit(void) const
Get the deficit for this flow.
void SetDeficit(uint32_t deficit)
Set the deficit for this flow.
int32_t m_deficit
the deficit for this flow
uint32_t GetIndex(void) const
Get the index of this flow.
FlowStatus m_status
the status of this flow
FlowStatus GetStatus(void) const
Get the status of 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.
virtual bool CheckConfig(void)
Check whether the current configuration is correct.
uint32_t m_setWays
size of a set of queues (used by set associative hash)
ObjectFactory m_queueDiscFactory
Factory to create a new queue.
static constexpr const char * UNCLASSIFIED_DROP
No packet filter able to classify packet.
virtual Ptr< QueueDiscItem > DoDequeue(void)
This function actually extracts a packet from the queue disc.
static constexpr const char * OVERLIMIT_DROP
Overlimit dropped packets.
ObjectFactory m_flowFactory
Factory to create a new flow.
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.
uint32_t GetQuantum(void) const
Get the quantum value.
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.
uint32_t FqCoDelDrop(void)
Drop a packet from the head of the queue with the largest current byte count.
virtual bool DoEnqueue(Ptr< QueueDiscItem > item)
This function actually enqueues a packet into the queue disc.
std::map< uint32_t, uint32_t > m_tags
Tags used by set associative hash.
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)
static TypeId GetTypeId(void)
Get the type ID.
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.
virtual void InitializeParams(void)
Initialize parameters (if any) before the first packet is enqueued.
uint32_t m_flows
Number of flow queues.
Network layer to device interface.
Definition: net-device.h:96
virtual uint16_t GetMtu(void) const =0
void SetAttribute(std::string name, const AttributeValue &value)
Set a single attribute, raising fatal errors if unsuccessful.
Definition: object-base.cc:256
void Set(const std::string &name, const AttributeValue &value, Args &&... args)
Set an attribute to be set during construction.
Ptr< Object > Create(void) const
Create an Object instance of the configured TypeId.
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:48
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:74
QueueDiscClass is the base class for classes that are included in a queue disc.
Definition: queue-disc.h:49
QueueDisc is an abstract base class providing the interface and implementing the operations common to...
Definition: queue-disc.h:181
QueueSize GetCurrentSize(void)
Get the current size of the queue disc in bytes, if operating in bytes mode, or packets,...
Definition: queue-disc.cc:521
void AddQueueDiscClass(Ptr< QueueDiscClass > qdClass)
Add a queue disc class to the tail of the list of classes.
Definition: queue-disc.cc:632
uint32_t GetNBytes(void) const
Get the amount of bytes stored by the queue disc.
Definition: queue-disc.cc:445
QueueSize GetMaxSize(void) const
Get the maximum size of the queue disc.
Definition: queue-disc.cc:452
Ptr< InternalQueue > GetInternalQueue(std::size_t i) const
Get the i-th internal queue.
Definition: queue-disc.cc:599
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:673
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
Ptr< NetDeviceQueueInterface > GetNetDeviceQueueInterface(void) const
Definition: queue-disc.cc:544
std::size_t GetNPacketFilters(void) const
Get the number of packet filters.
Definition: queue-disc.cc:626
Ptr< QueueDiscClass > GetQueueDiscClass(std::size_t i) const
Get the i-th queue disc class.
Definition: queue-disc.cc:660
std::size_t GetNQueueDiscClasses(void) const
Get the number of queue disc classes.
Definition: queue-disc.cc:667
bool SetMaxSize(QueueSize size)
Set the maximum size of the queue disc.
Definition: queue-disc.cc:480
std::size_t GetNInternalQueues(void) const
Get the number of internal queues.
Definition: queue-disc.cc:606
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:727
Class for representing queue sizes.
Definition: queue-size.h:95
AttributeValue implementation for QueueSize.
Hold variables of type string.
Definition: string.h:41
static Time Max()
Maximum representable Time Not to be confused with Max(Time,Time).
Definition: nstime.h:282
AttributeValue implementation for Time.
Definition: nstime.h:1308
a unique identifier for an interface.
Definition: type-id.h:59
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:922
Hold an unsigned integer type.
Definition: uinteger.h:44
Ptr< const AttributeChecker > MakeBooleanChecker(void)
Definition: boolean.cc:121
Ptr< const AttributeAccessor > MakeBooleanAccessor(T1 a1)
Definition: boolean.h:85
Ptr< const AttributeAccessor > MakeStringAccessor(T1 a1)
Definition: string.h:42
Ptr< const AttributeChecker > MakeStringChecker(void)
Definition: string.cc:30
Ptr< const AttributeAccessor > MakeTimeAccessor(T1 a1)
Definition: nstime.h:1309
Ptr< const AttributeAccessor > MakeUintegerAccessor(T1 a1)
Definition: uinteger.h:45
#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:257
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:273
#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:265
@ INACTIVE
Inactive Period or unslotted CSMA-CA.
Definition: lr-wpan-mac.h:93
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
QueueSizeUnit
Enumeration of the operating modes of queues.
Definition: queue-size.h:43
@ PACKETS
Use number of packets for queue size.
Definition: queue-size.h:44
QueueDiscSizePolicy
Enumeration of the available policies to handle the queue disc size.
Definition: queue-disc.h:104
@ MULTIPLE_QUEUES
Used by queue discs with multiple internal queues/child queue discs.
Definition: queue-disc.h:107
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Ptr< const AttributeChecker > MakeTimeChecker(const Time min, const Time max)
Helper to make a Time checker with bounded range.
Definition: time.cc:522