A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
fq-cobalt-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) 2020 NITK Surathkal (adapted for COBALT)
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 * Modified by: Bhaskar Kataria <bhaskar.k7920@gmail.com> (for COBALT)
21 * Tom Henderson <tomhend@u.washington.edu>
22 * Mohit P. Tahiliani <tahiliani@nitk.edu.in>
23 * Vivek Jain <jain.vivek.anand@gmail.com>
24 * Ankit Deepak <adadeepak8@gmail.com>
25 */
26
28
29#include "cobalt-queue-disc.h"
30
31#include "ns3/log.h"
32#include "ns3/net-device-queue-interface.h"
33#include "ns3/queue.h"
34#include "ns3/string.h"
35
36namespace ns3
37{
38
39NS_LOG_COMPONENT_DEFINE("FqCobaltQueueDisc");
40
41NS_OBJECT_ENSURE_REGISTERED(FqCobaltFlow);
42
43TypeId
45{
46 static TypeId tid = TypeId("ns3::FqCobaltFlow")
48 .SetGroupName("TrafficControl")
49 .AddConstructor<FqCobaltFlow>();
50 return tid;
51}
52
54 : m_deficit(0),
55 m_status(INACTIVE),
56 m_index(0)
57{
58 NS_LOG_FUNCTION(this);
59}
60
62{
63 NS_LOG_FUNCTION(this);
64}
65
66void
68{
69 NS_LOG_FUNCTION(this << deficit);
70 m_deficit = deficit;
71}
72
75{
76 NS_LOG_FUNCTION(this);
77 return m_deficit;
78}
79
80void
82{
83 NS_LOG_FUNCTION(this << deficit);
84 m_deficit += deficit;
85}
86
87void
89{
90 NS_LOG_FUNCTION(this);
91 m_status = status;
92}
93
96{
97 NS_LOG_FUNCTION(this);
98 return m_status;
99}
100
101void
103{
104 NS_LOG_FUNCTION(this);
105 m_index = index;
106}
107
110{
111 return m_index;
112}
113
115
116TypeId
118{
119 static TypeId tid =
120 TypeId("ns3::FqCobaltQueueDisc")
122 .SetGroupName("TrafficControl")
123 .AddConstructor<FqCobaltQueueDisc>()
124 .AddAttribute("UseEcn",
125 "True to use ECN (packets are marked instead of being dropped)",
126 BooleanValue(true),
129 .AddAttribute("Interval",
130 "The CoDel algorithm interval for each FqCobalt queue",
131 StringValue("100ms"),
134 .AddAttribute("Target",
135 "The CoDel algorithm target queue delay for each FqCobalt queue",
136 StringValue("5ms"),
139 .AddAttribute("MaxSize",
140 "The maximum number of packets accepted by this queue disc",
141 QueueSizeValue(QueueSize("10240p")),
142 MakeQueueSizeAccessor(&QueueDisc::SetMaxSize, &QueueDisc::GetMaxSize),
143 MakeQueueSizeChecker())
144 .AddAttribute("Flows",
145 "The number of queues into which the incoming packets are classified",
146 UintegerValue(1024),
148 MakeUintegerChecker<uint32_t>())
149 .AddAttribute("DropBatchSize",
150 "The maximum number of packets dropped from the fat flow",
151 UintegerValue(64),
153 MakeUintegerChecker<uint32_t>())
154 .AddAttribute("Perturbation",
155 "The salt used as an additional input to the hash function used to "
156 "classify packets",
157 UintegerValue(0),
159 MakeUintegerChecker<uint32_t>())
160 .AddAttribute("CeThreshold",
161 "The FqCobalt CE threshold for marking packets",
165 .AddAttribute("EnableSetAssociativeHash",
166 "Enable/Disable Set Associative Hash",
167 BooleanValue(false),
170 .AddAttribute("SetWays",
171 "The size of a set of queues (used by set associative hash)",
172 UintegerValue(8),
174 MakeUintegerChecker<uint32_t>())
175 .AddAttribute("UseL4s",
176 "True to use L4S (only ECT1 packets are marked at CE threshold)",
177 BooleanValue(false),
180 .AddAttribute("Pdrop",
181 "Marking Probability",
182 DoubleValue(0),
184 MakeDoubleChecker<double>())
185 .AddAttribute("Increment",
186 "Pdrop increment value",
187 DoubleValue(1. / 256),
189 MakeDoubleChecker<double>())
190 .AddAttribute("Decrement",
191 "Pdrop decrement Value",
192 DoubleValue(1. / 4096),
194 MakeDoubleChecker<double>())
195 .AddAttribute("BlueThreshold",
196 "The Threshold after which Blue is enabled",
200 return tid;
201}
202
205 m_quantum(0)
206{
207 NS_LOG_FUNCTION(this);
208}
209
211{
212 NS_LOG_FUNCTION(this);
213}
214
215void
217{
218 NS_LOG_FUNCTION(this << quantum);
219 m_quantum = quantum;
220}
221
224{
225 return m_quantum;
226}
227
230{
231 NS_LOG_FUNCTION(this << flowHash);
232
233 uint32_t h = (flowHash % m_flows);
234 uint32_t innerHash = h % m_setWays;
235 uint32_t outerHash = h - innerHash;
236
237 for (uint32_t i = outerHash; i < outerHash + m_setWays; i++)
238 {
239 auto it = m_flowsIndices.find(i);
240
241 if (it == m_flowsIndices.end() ||
242 (m_tags.find(i) != m_tags.end() && m_tags[i] == flowHash) ||
243 StaticCast<FqCobaltFlow>(GetQueueDiscClass(it->second))->GetStatus() ==
245 {
246 // this queue has not been created yet or is associated with this flow
247 // or is inactive, hence we can use it
248 m_tags[i] = flowHash;
249 return i;
250 }
251 }
252
253 // all the queues of the set are used. Use the first queue of the set
254 m_tags[outerHash] = flowHash;
255 return outerHash;
256}
257
258bool
260{
261 NS_LOG_FUNCTION(this << item);
262
263 uint32_t flowHash;
264 uint32_t h;
265
266 if (GetNPacketFilters() == 0)
267 {
268 flowHash = item->Hash(m_perturbation);
269 }
270 else
271 {
272 int32_t ret = Classify(item);
273
274 if (ret != PacketFilter::PF_NO_MATCH)
275 {
276 flowHash = static_cast<uint32_t>(ret);
277 }
278 else
279 {
280 NS_LOG_ERROR("No filter has been able to classify this packet, drop it.");
282 return false;
283 }
284 }
285
287 {
288 h = SetAssociativeHash(flowHash);
289 }
290 else
291 {
292 h = flowHash % m_flows;
293 }
294
296 if (m_flowsIndices.find(h) == m_flowsIndices.end())
297 {
298 NS_LOG_DEBUG("Creating a new flow queue with index " << h);
301 // If Cobalt, Set values of CobaltQueueDisc to match this QueueDisc
302 Ptr<CobaltQueueDisc> cobalt = qd->GetObject<CobaltQueueDisc>();
303 if (cobalt)
304 {
305 cobalt->SetAttribute("UseEcn", BooleanValue(m_useEcn));
306 cobalt->SetAttribute("CeThreshold", TimeValue(m_ceThreshold));
307 cobalt->SetAttribute("UseL4s", BooleanValue(m_useL4s));
308 cobalt->SetAttribute("BlueThreshold", TimeValue(m_blueThreshold));
309 }
310 qd->Initialize();
311 flow->SetQueueDisc(qd);
312 flow->SetIndex(h);
313 AddQueueDiscClass(flow);
314
316 }
317 else
318 {
319 flow = StaticCast<FqCobaltFlow>(GetQueueDiscClass(m_flowsIndices[h]));
320 }
321
322 if (flow->GetStatus() == FqCobaltFlow::INACTIVE)
323 {
324 flow->SetStatus(FqCobaltFlow::NEW_FLOW);
325 flow->SetDeficit(m_quantum);
326 m_newFlows.push_back(flow);
327 }
328
329 flow->GetQueueDisc()->Enqueue(item);
330
331 NS_LOG_DEBUG("Packet enqueued into flow " << h << "; flow index " << m_flowsIndices[h]);
332
333 if (GetCurrentSize() > GetMaxSize())
334 {
335 NS_LOG_DEBUG("Overload; enter FqCobaltDrop ()");
336 FqCobaltDrop();
337 }
338
339 return true;
340}
341
344{
345 NS_LOG_FUNCTION(this);
346
349
350 do
351 {
352 bool found = false;
353
354 while (!found && !m_newFlows.empty())
355 {
356 flow = m_newFlows.front();
357
358 if (flow->GetDeficit() <= 0)
359 {
360 NS_LOG_DEBUG("Increase deficit for new flow index " << flow->GetIndex());
361 flow->IncreaseDeficit(m_quantum);
362 flow->SetStatus(FqCobaltFlow::OLD_FLOW);
363 m_oldFlows.push_back(flow);
364 m_newFlows.pop_front();
365 }
366 else
367 {
368 NS_LOG_DEBUG("Found a new flow " << flow->GetIndex() << " with positive deficit");
369 found = true;
370 }
371 }
372
373 while (!found && !m_oldFlows.empty())
374 {
375 flow = m_oldFlows.front();
376
377 if (flow->GetDeficit() <= 0)
378 {
379 NS_LOG_DEBUG("Increase deficit for old flow index " << flow->GetIndex());
380 flow->IncreaseDeficit(m_quantum);
381 m_oldFlows.push_back(flow);
382 m_oldFlows.pop_front();
383 }
384 else
385 {
386 NS_LOG_DEBUG("Found an old flow " << flow->GetIndex() << " with positive deficit");
387 found = true;
388 }
389 }
390
391 if (!found)
392 {
393 NS_LOG_DEBUG("No flow found to dequeue a packet");
394 return nullptr;
395 }
396
397 item = flow->GetQueueDisc()->Dequeue();
398
399 if (!item)
400 {
401 NS_LOG_DEBUG("Could not get a packet from the selected flow queue");
402 if (!m_newFlows.empty())
403 {
404 flow->SetStatus(FqCobaltFlow::OLD_FLOW);
405 m_oldFlows.push_back(flow);
406 m_newFlows.pop_front();
407 }
408 else
409 {
410 flow->SetStatus(FqCobaltFlow::INACTIVE);
411 m_oldFlows.pop_front();
412 }
413 }
414 else
415 {
416 NS_LOG_DEBUG("Dequeued packet " << item->GetPacket());
417 }
418 } while (!item);
419
420 flow->IncreaseDeficit(item->GetSize() * -1);
421
422 return item;
423}
424
425bool
427{
428 NS_LOG_FUNCTION(this);
429 if (GetNQueueDiscClasses() > 0)
430 {
431 NS_LOG_ERROR("FqCobaltQueueDisc cannot have classes");
432 return false;
433 }
434
435 if (GetNInternalQueues() > 0)
436 {
437 NS_LOG_ERROR("FqCobaltQueueDisc cannot have internal queues");
438 return false;
439 }
440 // we are at initialization time. If the user has not set a quantum value,
441 // set the quantum to the MTU of the device (if any)
442 if (!m_quantum)
443 {
445 Ptr<NetDevice> dev;
446 // if the NetDeviceQueueInterface object is aggregated to a
447 // NetDevice, get the MTU of such NetDevice
448 if (ndqi && (dev = ndqi->GetObject<NetDevice>()))
449 {
450 m_quantum = dev->GetMtu();
451 NS_LOG_DEBUG("Setting the quantum to the MTU of the device: " << m_quantum);
452 }
453
454 if (!m_quantum)
455 {
456 NS_LOG_ERROR("The quantum parameter cannot be null");
457 return false;
458 }
459 }
460
462 {
463 NS_LOG_ERROR("The number of queues must be an integer multiple of the size "
464 "of the set of queues used by set associative hash");
465 return false;
466 }
467
468 // If UseL4S attribute is enabled then CE threshold must be set.
469 if (m_useL4s)
470 {
471 NS_ABORT_MSG_IF(m_ceThreshold == Time::Max(), "CE threshold not set");
472 if (!m_useEcn)
473 {
474 NS_LOG_WARN("Enabling ECN as L4S mode is enabled");
475 }
476 }
477 return true;
478}
479
480void
482{
483 NS_LOG_FUNCTION(this);
484
485 m_flowFactory.SetTypeId("ns3::FqCobaltFlow");
486
487 m_queueDiscFactory.SetTypeId("ns3::CobaltQueueDisc");
494}
495
498{
499 NS_LOG_FUNCTION(this);
500
501 uint32_t maxBacklog = 0;
502 uint32_t index = 0;
504
505 /* Queue is full! Find the fat flow and drop packet(s) from it */
506 for (uint32_t i = 0; i < GetNQueueDiscClasses(); i++)
507 {
508 qd = GetQueueDiscClass(i)->GetQueueDisc();
509 uint32_t bytes = qd->GetNBytes();
510 if (bytes > maxBacklog)
511 {
512 maxBacklog = bytes;
513 index = i;
514 }
515 }
516
517 /* Our goal is to drop half of this fat flow backlog */
518 uint32_t len = 0;
519 uint32_t count = 0;
520 uint32_t threshold = maxBacklog >> 1;
521 qd = GetQueueDiscClass(index)->GetQueueDisc();
523
524 do
525 {
526 NS_LOG_DEBUG("Drop packet (overflow); count: " << count << " len: " << len
527 << " threshold: " << threshold);
528 item = qd->GetInternalQueue(0)->Dequeue();
530 len += item->GetSize();
531 } while (++count < m_dropBatchSize && len < threshold);
532
533 return index;
534}
535
536} // namespace ns3
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:42
A flow queue used by the FqCobalt queue disc.
FlowStatus GetStatus() 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
int32_t GetDeficit() const
Get the deficit for this flow.
uint32_t GetIndex() const
Get the index of this flow.
FlowStatus
Used to determine the status of this flow queue.
static TypeId GetTypeId()
Get the type ID.
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.
bool m_useL4s
True if L4S is used (ECT1 packets are marked at CE threshold)
Ptr< QueueDiscItem > DoDequeue() override
This function actually extracts a packet from the queue disc.
bool CheckConfig() override
Check whether the current configuration is correct.
bool DoEnqueue(Ptr< QueueDiscItem > item) override
This function actually enqueues a packet into the queue disc.
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.
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
void InitializeParams() override
Initialize parameters (if any) before the first packet is enqueued.
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.
uint32_t FqCobaltDrop()
Drop a packet from the head of the queue with the largest current byte count.
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()
Get the type ID.
uint32_t GetQuantum() const
Get the quantum value.
uint32_t m_setWays
size of a set of queues (used by set associative hash)
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 AttributeAccessor > MakeDoubleAccessor(T1 a1)
Definition: double.h:43
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
Time MilliSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition: nstime.h:1348
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.