A Discrete-Event Network Simulator
API
fq-cobalt-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 * Copyright (c) 2020 NITK Surathkal (adapted for COBALT)
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 as
8 * published by the Free Software Foundation;
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 *
19 * Authors: Pasquale Imputato <p.imputato@gmail.com>
20 * Stefano Avallone <stefano.avallone@unina.it>
21 * Modified by: Bhaskar Kataria <bhaskar.k7920@gmail.com> (for COBALT)
22 * Tom Henderson <tomhend@u.washington.edu>
23 * Mohit P. Tahiliani <tahiliani@nitk.edu.in>
24 * Vivek Jain <jain.vivek.anand@gmail.com>
25 * Ankit Deepak <adadeepak8@gmail.com>
26 */
27
28#include "ns3/log.h"
29#include "ns3/string.h"
30#include "ns3/queue.h"
32#include "cobalt-queue-disc.h"
33#include "ns3/net-device-queue-interface.h"
34
35namespace ns3 {
36
37NS_LOG_COMPONENT_DEFINE ("FqCobaltQueueDisc");
38
39NS_OBJECT_ENSURE_REGISTERED (FqCobaltFlow);
40
42{
43 static TypeId tid = TypeId ("ns3::FqCobaltFlow")
45 .SetGroupName ("TrafficControl")
46 .AddConstructor<FqCobaltFlow> ()
47 ;
48 return tid;
49}
50
52 : m_deficit (0),
53 m_status (INACTIVE),
54 m_index (0)
55{
56 NS_LOG_FUNCTION (this);
57}
58
60{
61 NS_LOG_FUNCTION (this);
62}
63
64void
66{
67 NS_LOG_FUNCTION (this << deficit);
68 m_deficit = deficit;
69}
70
73{
74 NS_LOG_FUNCTION (this);
75 return m_deficit;
76}
77
78void
80{
81 NS_LOG_FUNCTION (this << deficit);
82 m_deficit += deficit;
83}
84
85void
87{
88 NS_LOG_FUNCTION (this);
89 m_status = status;
90}
91
94{
95 NS_LOG_FUNCTION (this);
96 return m_status;
97}
98
99void
101{
102 NS_LOG_FUNCTION (this);
103 m_index = index;
104}
105
108{
109 return m_index;
110}
111
112
114
116{
117 static TypeId tid = TypeId ("ns3::FqCobaltQueueDisc")
119 .SetGroupName ("TrafficControl")
120 .AddConstructor<FqCobaltQueueDisc> ()
121 .AddAttribute ("UseEcn",
122 "True to use ECN (packets are marked instead of being dropped)",
123 BooleanValue (true),
126 .AddAttribute ("Interval",
127 "The CoDel algorithm interval for each FqCobalt queue",
128 StringValue ("100ms"),
131 .AddAttribute ("Target",
132 "The CoDel algorithm target queue delay for each FqCobalt queue",
133 StringValue ("5ms"),
136 .AddAttribute ("MaxSize",
137 "The maximum number of packets accepted by this queue disc",
138 QueueSizeValue (QueueSize ("10240p")),
139 MakeQueueSizeAccessor (&QueueDisc::SetMaxSize,
141 MakeQueueSizeChecker ())
142 .AddAttribute ("Flows",
143 "The number of queues into which the incoming packets are classified",
144 UintegerValue (1024),
146 MakeUintegerChecker<uint32_t> ())
147 .AddAttribute ("DropBatchSize",
148 "The maximum number of packets dropped from the fat flow",
149 UintegerValue (64),
151 MakeUintegerChecker<uint32_t> ())
152 .AddAttribute ("Perturbation",
153 "The salt used as an additional input to the hash function used to classify packets",
154 UintegerValue (0),
156 MakeUintegerChecker<uint32_t> ())
157 .AddAttribute ("CeThreshold",
158 "The FqCobalt CE threshold for marking packets",
159 TimeValue (Time::Max ()),
162 .AddAttribute ("EnableSetAssociativeHash",
163 "Enable/Disable Set Associative Hash",
164 BooleanValue (false),
167 .AddAttribute ("SetWays",
168 "The size of a set of queues (used by set associative hash)",
169 UintegerValue (8),
171 MakeUintegerChecker<uint32_t> ())
172 .AddAttribute ("UseL4s",
173 "True to use L4S (only ECT1 packets are marked at CE threshold)",
174 BooleanValue (false),
177 .AddAttribute ("Pdrop",
178 "Marking Probability",
179 DoubleValue (0),
181 MakeDoubleChecker<double> ())
182 .AddAttribute ("Increment",
183 "Pdrop increment value",
184 DoubleValue (1. / 256),
186 MakeDoubleChecker<double> ())
187 .AddAttribute ("Decrement",
188 "Pdrop decrement Value",
189 DoubleValue (1. / 4096),
191 MakeDoubleChecker<double> ())
192 .AddAttribute ("BlueThreshold",
193 "The Threshold after which Blue is enabled",
194 TimeValue (MilliSeconds (400)),
197 ;
198 return tid;
199}
200
203 m_quantum (0)
204{
205 NS_LOG_FUNCTION (this);
206}
207
209{
210 NS_LOG_FUNCTION (this);
211}
212
213void
215{
216 NS_LOG_FUNCTION (this << quantum);
217 m_quantum = quantum;
218}
219
222{
223 return m_quantum;
224}
225
228{
229 NS_LOG_FUNCTION (this << flowHash);
230
231 uint32_t h = (flowHash % m_flows);
232 uint32_t innerHash = h % m_setWays;
233 uint32_t outerHash = h - innerHash;
234
235 for (uint32_t i = outerHash; i < outerHash + m_setWays; i++)
236 {
237 auto it = m_flowsIndices.find (i);
238
239 if (it == m_flowsIndices.end ()
240 || (m_tags.find (i) != m_tags.end () && m_tags[i] == flowHash)
241 || StaticCast<FqCobaltFlow> (GetQueueDiscClass (it->second))->GetStatus () == FqCobaltFlow::INACTIVE)
242 {
243 // this queue has not been created yet or is associated with this flow
244 // or is inactive, hence we can use it
245 m_tags[i] = flowHash;
246 return i;
247 }
248 }
249
250 // all the queues of the set are used. Use the first queue of the set
251 m_tags[outerHash] = flowHash;
252 return outerHash;
253}
254
255bool
257{
258 NS_LOG_FUNCTION (this << item);
259
260 uint32_t flowHash, h;
261
262 if (GetNPacketFilters () == 0)
263 {
264 flowHash = item->Hash (m_perturbation);
265 }
266 else
267 {
268 int32_t ret = Classify (item);
269
270 if (ret != PacketFilter::PF_NO_MATCH)
271 {
272 flowHash = static_cast<uint32_t> (ret);
273 }
274 else
275 {
276 NS_LOG_ERROR ("No filter has been able to classify this packet, drop it.");
278 return false;
279 }
280 }
281
283 {
284 h = SetAssociativeHash (flowHash);
285 }
286 else
287 {
288 h = flowHash % m_flows;
289 }
290
292 if (m_flowsIndices.find (h) == m_flowsIndices.end ())
293 {
294 NS_LOG_DEBUG ("Creating a new flow queue with index " << h);
297 // If Cobalt, Set values of CobaltQueueDisc to match this QueueDisc
298 Ptr<CobaltQueueDisc> cobalt = qd->GetObject<CobaltQueueDisc> ();
299 if (cobalt)
300 {
301 cobalt->SetAttribute ("UseEcn", BooleanValue (m_useEcn));
302 cobalt->SetAttribute ("CeThreshold", TimeValue (m_ceThreshold));
303 cobalt->SetAttribute ("UseL4s", BooleanValue (m_useL4s));
304 cobalt->SetAttribute ("BlueThreshold", TimeValue (m_blueThreshold));
305 }
306 qd->Initialize ();
307 flow->SetQueueDisc (qd);
308 flow->SetIndex (h);
309 AddQueueDiscClass (flow);
310
312 }
313 else
314 {
315 flow = StaticCast<FqCobaltFlow> (GetQueueDiscClass (m_flowsIndices[h]));
316 }
317
318 if (flow->GetStatus () == FqCobaltFlow::INACTIVE)
319 {
320 flow->SetStatus (FqCobaltFlow::NEW_FLOW);
321 flow->SetDeficit (m_quantum);
322 m_newFlows.push_back (flow);
323 }
324
325 flow->GetQueueDisc ()->Enqueue (item);
326
327 NS_LOG_DEBUG ("Packet enqueued into flow " << h << "; flow index " << m_flowsIndices[h]);
328
329 if (GetCurrentSize () > GetMaxSize ())
330 {
331 NS_LOG_DEBUG ("Overload; enter FqCobaltDrop ()");
332 FqCobaltDrop ();
333 }
334
335 return true;
336}
337
340{
341 NS_LOG_FUNCTION (this);
342
345
346 do
347 {
348 bool found = false;
349
350 while (!found && !m_newFlows.empty ())
351 {
352 flow = m_newFlows.front ();
353
354 if (flow->GetDeficit () <= 0)
355 {
356 NS_LOG_DEBUG ("Increase deficit for new flow index " << flow->GetIndex ());
357 flow->IncreaseDeficit (m_quantum);
358 flow->SetStatus (FqCobaltFlow::OLD_FLOW);
359 m_oldFlows.push_back (flow);
360 m_newFlows.pop_front ();
361 }
362 else
363 {
364 NS_LOG_DEBUG ("Found a new flow " << flow->GetIndex () << " with positive deficit");
365 found = true;
366 }
367 }
368
369 while (!found && !m_oldFlows.empty ())
370 {
371 flow = m_oldFlows.front ();
372
373 if (flow->GetDeficit () <= 0)
374 {
375 NS_LOG_DEBUG ("Increase deficit for old flow index " << flow->GetIndex ());
376 flow->IncreaseDeficit (m_quantum);
377 m_oldFlows.push_back (flow);
378 m_oldFlows.pop_front ();
379 }
380 else
381 {
382 NS_LOG_DEBUG ("Found an old flow " << flow->GetIndex () << " with positive deficit");
383 found = true;
384 }
385 }
386
387 if (!found)
388 {
389 NS_LOG_DEBUG ("No flow found to dequeue a packet");
390 return 0;
391 }
392
393 item = flow->GetQueueDisc ()->Dequeue ();
394
395 if (!item)
396 {
397 NS_LOG_DEBUG ("Could not get a packet from the selected flow queue");
398 if (!m_newFlows.empty ())
399 {
400 flow->SetStatus (FqCobaltFlow::OLD_FLOW);
401 m_oldFlows.push_back (flow);
402 m_newFlows.pop_front ();
403 }
404 else
405 {
406 flow->SetStatus (FqCobaltFlow::INACTIVE);
407 m_oldFlows.pop_front ();
408 }
409 }
410 else
411 {
412 NS_LOG_DEBUG ("Dequeued packet " << item->GetPacket ());
413 }
414 }
415 while (item == 0);
416
417 flow->IncreaseDeficit (item->GetSize () * -1);
418
419 return item;
420}
421
422bool
424{
425 NS_LOG_FUNCTION (this);
426 if (GetNQueueDiscClasses () > 0)
427 {
428 NS_LOG_ERROR ("FqCobaltQueueDisc cannot have classes");
429 return false;
430 }
431
432 if (GetNInternalQueues () > 0)
433 {
434 NS_LOG_ERROR ("FqCobaltQueueDisc cannot have internal queues");
435 return false;
436 }
437 // we are at initialization time. If the user has not set a quantum value,
438 // set the quantum to the MTU of the device (if any)
439 if (!m_quantum)
440 {
442 Ptr<NetDevice> dev;
443 // if the NetDeviceQueueInterface object is aggregated to a
444 // NetDevice, get the MTU of such NetDevice
445 if (ndqi && (dev = ndqi->GetObject<NetDevice> ()))
446 {
447 m_quantum = dev->GetMtu ();
448 NS_LOG_DEBUG ("Setting the quantum to the MTU of the device: " << m_quantum);
449 }
450
451 if (!m_quantum)
452 {
453 NS_LOG_ERROR ("The quantum parameter cannot be null");
454 return false;
455 }
456 }
457
459 {
460 NS_LOG_ERROR ("The number of queues must be an integer multiple of the size "
461 "of the set of queues used by set associative hash");
462 return false;
463 }
464
465 // If UseL4S attribute is enabled then CE threshold must be set.
466 if (m_useL4s)
467 {
468 NS_ABORT_MSG_IF (m_ceThreshold == Time::Max (), "CE threshold not set");
469 if (m_useEcn == false)
470 {
471 NS_LOG_WARN ("Enabling ECN as L4S mode is enabled");
472 }
473 }
474 return true;
475}
476
477void
479{
480 NS_LOG_FUNCTION (this);
481
482 m_flowFactory.SetTypeId ("ns3::FqCobaltFlow");
483
484 m_queueDiscFactory.SetTypeId ("ns3::CobaltQueueDisc");
491}
492
495{
496 NS_LOG_FUNCTION (this);
497
498 uint32_t maxBacklog = 0, index = 0;
500
501 /* Queue is full! Find the fat flow and drop packet(s) from it */
502 for (uint32_t i = 0; i < GetNQueueDiscClasses (); i++)
503 {
504 qd = GetQueueDiscClass (i)->GetQueueDisc ();
505 uint32_t bytes = qd->GetNBytes ();
506 if (bytes > maxBacklog)
507 {
508 maxBacklog = bytes;
509 index = i;
510 }
511 }
512
513 /* Our goal is to drop half of this fat flow backlog */
514 uint32_t len = 0, count = 0, threshold = maxBacklog >> 1;
515 qd = GetQueueDiscClass (index)->GetQueueDisc ();
517
518 do
519 {
520 NS_LOG_DEBUG ("Drop packet (overflow); count: " << count << " len: " << len << " threshold: " << threshold);
521 item = qd->GetInternalQueue (0)->Dequeue ();
523 len += item->GetSize ();
524 }
525 while (++count < m_dropBatchSize && len < threshold);
526
527 return index;
528}
529
530} // namespace ns3
531
AttributeValue implementation for Boolean.
Definition: boolean.h:37
Cobalt packet queue disc.
This class can be used to hold variables of floating point type such as 'double' or 'float'.
Definition: double.h:41
A flow queue used by the FqCobalt queue disc.
int32_t GetDeficit(void) const
Get the deficit for this flow.
uint32_t GetIndex(void) const
Get the index of this flow.
FlowStatus GetStatus(void) const
Get the status of this flow.
void SetDeficit(uint32_t deficit)
Set the deficit for this flow.
FqCobaltFlow()
FqCobaltFlow constructor.
void SetIndex(uint32_t index)
Set the index for this flow.
void IncreaseDeficit(int32_t deficit)
Increase the deficit for this flow.
int32_t m_deficit
the deficit for this flow
uint32_t m_index
the index for this flow
static TypeId GetTypeId(void)
Get the type ID.
FlowStatus
Used to determine the status of this flow queue.
FlowStatus m_status
the status of this flow
void SetStatus(FlowStatus status)
Set the status for this flow.
A FqCobalt packet queue disc.
ObjectFactory m_flowFactory
Factory to create a new flow.
std::map< uint32_t, uint32_t > m_tags
Tags used by set associative hash.
uint32_t GetQuantum(void) const
Get the quantum value.
bool m_useL4s
True if L4S is used (ECT1 packets are marked at CE threshold)
Time m_ceThreshold
Threshold above which to CE mark.
bool m_enableSetAssociativeHash
whether to enable set associative hash
std::map< uint32_t, uint32_t > m_flowsIndices
Map with the index of class for each flow.
uint32_t FqCobaltDrop(void)
Drop a packet from the head of the queue with the largest current byte count.
virtual bool CheckConfig(void)
Check whether the current configuration is correct.
std::list< Ptr< FqCobaltFlow > > m_newFlows
The list of new flows.
uint32_t m_quantum
Deficit assigned to flows at each round.
std::list< Ptr< FqCobaltFlow > > m_oldFlows
The list of old flows.
bool m_useEcn
True if ECN is used (packets are marked instead of being dropped)
uint32_t SetAssociativeHash(uint32_t flowHash)
Compute the index of the queue for the flow having the given flowHash, according to the set associati...
std::string m_target
CoDel target attribute.
uint32_t m_perturbation
hash perturbation value
FqCobaltQueueDisc()
FqCobaltQueueDisc constructor.
uint32_t m_dropBatchSize
Max number of packets dropped from the fat flow.
double m_increment
increment value for marking probability
std::string m_interval
CoDel interval attribute.
static constexpr const char * OVERLIMIT_DROP
Overlimit dropped packets.
double m_decrement
decrement value for marking probability
static constexpr const char * UNCLASSIFIED_DROP
No packet filter able to classify packet.
void SetQuantum(uint32_t quantum)
Set the quantum value.
Time m_blueThreshold
Threshold to enable blue enhancement.
virtual void InitializeParams(void)
Initialize parameters (if any) before the first packet is enqueued.
virtual Ptr< QueueDiscItem > DoDequeue(void)
This function actually extracts a packet from the queue disc.
ObjectFactory m_queueDiscFactory
Factory to create a new queue.
double m_Pdrop
Drop Probability.
uint32_t m_flows
Number of flow queues.
static TypeId GetTypeId(void)
Get the type ID.
virtual bool DoEnqueue(Ptr< QueueDiscItem > item)
This function actually enqueues a packet into the queue disc.
uint32_t m_setWays
size of a set of queues (used by set associative hash)
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 > MakeDoubleAccessor(T1 a1)
Definition: double.h:42
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
Time MilliSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition: nstime.h:1252
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