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 * SPDX-License-Identifier: GPL-2.0-only
6 *
7 * Authors: Pasquale Imputato <p.imputato@gmail.com>
8 * Stefano Avallone <stefano.avallone@unina.it>
9 * Modified by: Bhaskar Kataria <bhaskar.k7920@gmail.com> (for COBALT)
10 * Tom Henderson <tomhend@u.washington.edu>
11 * Mohit P. Tahiliani <tahiliani@nitk.edu.in>
12 * Vivek Jain <jain.vivek.anand@gmail.com>
13 * Ankit Deepak <adadeepak8@gmail.com>
14 */
15
17
18#include "cobalt-queue-disc.h"
19
20#include "ns3/log.h"
21#include "ns3/net-device-queue-interface.h"
22#include "ns3/queue.h"
23#include "ns3/string.h"
24
25namespace ns3
26{
27
28NS_LOG_COMPONENT_DEFINE("FqCobaltQueueDisc");
29
30NS_OBJECT_ENSURE_REGISTERED(FqCobaltFlow);
31
32TypeId
34{
35 static TypeId tid = TypeId("ns3::FqCobaltFlow")
37 .SetGroupName("TrafficControl")
38 .AddConstructor<FqCobaltFlow>();
39 return tid;
40}
41
43 : m_deficit(0),
44 m_status(INACTIVE),
45 m_index(0)
46{
47 NS_LOG_FUNCTION(this);
48}
49
54
55void
57{
58 NS_LOG_FUNCTION(this << deficit);
59 m_deficit = deficit;
60}
61
64{
65 NS_LOG_FUNCTION(this);
66 return m_deficit;
67}
68
69void
71{
72 NS_LOG_FUNCTION(this << deficit);
73 m_deficit += deficit;
74}
75
76void
78{
79 NS_LOG_FUNCTION(this);
80 m_status = status;
81}
82
85{
86 NS_LOG_FUNCTION(this);
87 return m_status;
88}
89
90void
92{
93 NS_LOG_FUNCTION(this);
94 m_index = index;
95}
96
99{
100 return m_index;
101}
102
104
105TypeId
107{
108 static TypeId tid =
109 TypeId("ns3::FqCobaltQueueDisc")
111 .SetGroupName("TrafficControl")
112 .AddConstructor<FqCobaltQueueDisc>()
113 .AddAttribute("UseEcn",
114 "True to use ECN (packets are marked instead of being dropped)",
115 BooleanValue(true),
118 .AddAttribute("Interval",
119 "The CoDel algorithm interval for each FqCobalt queue",
120 StringValue("100ms"),
123 .AddAttribute("Target",
124 "The CoDel algorithm target queue delay for each FqCobalt queue",
125 StringValue("5ms"),
128 .AddAttribute("MaxSize",
129 "The maximum number of packets accepted by this queue disc",
130 QueueSizeValue(QueueSize("10240p")),
133 .AddAttribute("Flows",
134 "The number of queues into which the incoming packets are classified",
135 UintegerValue(1024),
138 .AddAttribute("DropBatchSize",
139 "The maximum number of packets dropped from the fat flow",
140 UintegerValue(64),
143 .AddAttribute("Perturbation",
144 "The salt used as an additional input to the hash function used to "
145 "classify packets",
146 UintegerValue(0),
149 .AddAttribute("CeThreshold",
150 "The FqCobalt CE threshold for marking packets",
154 .AddAttribute("EnableSetAssociativeHash",
155 "Enable/Disable Set Associative Hash",
156 BooleanValue(false),
159 .AddAttribute("SetWays",
160 "The size of a set of queues (used by set associative hash)",
161 UintegerValue(8),
164 .AddAttribute("UseL4s",
165 "True to use L4S (only ECT1 packets are marked at CE threshold)",
166 BooleanValue(false),
169 .AddAttribute("Pdrop",
170 "Marking Probability",
171 DoubleValue(0),
174 .AddAttribute("Increment",
175 "Pdrop increment value",
176 DoubleValue(1. / 256),
179 .AddAttribute("Decrement",
180 "Pdrop decrement Value",
181 DoubleValue(1. / 4096),
184 .AddAttribute("BlueThreshold",
185 "The Threshold after which Blue is enabled",
189 return tid;
190}
191
198
203
204void
206{
207 NS_LOG_FUNCTION(this << quantum);
208 m_quantum = quantum;
209}
210
213{
214 return m_quantum;
215}
216
219{
220 NS_LOG_FUNCTION(this << flowHash);
221
222 uint32_t h = (flowHash % m_flows);
223 uint32_t innerHash = h % m_setWays;
224 uint32_t outerHash = h - innerHash;
225
226 for (uint32_t i = outerHash; i < outerHash + m_setWays; i++)
227 {
228 auto it = m_flowsIndices.find(i);
229
230 if (it == m_flowsIndices.end() ||
231 (m_tags.find(i) != m_tags.end() && m_tags[i] == flowHash) ||
232 StaticCast<FqCobaltFlow>(GetQueueDiscClass(it->second))->GetStatus() ==
234 {
235 // this queue has not been created yet or is associated with this flow
236 // or is inactive, hence we can use it
237 m_tags[i] = flowHash;
238 return i;
239 }
240 }
241
242 // all the queues of the set are used. Use the first queue of the set
243 m_tags[outerHash] = flowHash;
244 return outerHash;
245}
246
247bool
249{
250 NS_LOG_FUNCTION(this << item);
251
252 uint32_t flowHash;
253 uint32_t h;
254
255 if (GetNPacketFilters() == 0)
256 {
257 flowHash = item->Hash(m_perturbation);
258 }
259 else
260 {
261 int32_t ret = Classify(item);
262
263 if (ret != PacketFilter::PF_NO_MATCH)
264 {
265 flowHash = static_cast<uint32_t>(ret);
266 }
267 else
268 {
269 NS_LOG_ERROR("No filter has been able to classify this packet, drop it.");
271 return false;
272 }
273 }
274
276 {
277 h = SetAssociativeHash(flowHash);
278 }
279 else
280 {
281 h = flowHash % m_flows;
282 }
283
285 if (m_flowsIndices.find(h) == m_flowsIndices.end())
286 {
287 NS_LOG_DEBUG("Creating a new flow queue with index " << h);
290 // If Cobalt, Set values of CobaltQueueDisc to match this QueueDisc
291 Ptr<CobaltQueueDisc> cobalt = qd->GetObject<CobaltQueueDisc>();
292 if (cobalt)
293 {
294 cobalt->SetAttribute("UseEcn", BooleanValue(m_useEcn));
295 cobalt->SetAttribute("CeThreshold", TimeValue(m_ceThreshold));
296 cobalt->SetAttribute("UseL4s", BooleanValue(m_useL4s));
297 cobalt->SetAttribute("BlueThreshold", TimeValue(m_blueThreshold));
298 }
299 qd->Initialize();
300 flow->SetQueueDisc(qd);
301 flow->SetIndex(h);
302 AddQueueDiscClass(flow);
303
305 }
306 else
307 {
309 }
310
311 if (flow->GetStatus() == FqCobaltFlow::INACTIVE)
312 {
313 flow->SetStatus(FqCobaltFlow::NEW_FLOW);
314 flow->SetDeficit(m_quantum);
315 m_newFlows.push_back(flow);
316 }
317
318 flow->GetQueueDisc()->Enqueue(item);
319
320 NS_LOG_DEBUG("Packet enqueued into flow " << h << "; flow index " << m_flowsIndices[h]);
321
322 if (GetCurrentSize() > GetMaxSize())
323 {
324 NS_LOG_DEBUG("Overload; enter FqCobaltDrop ()");
325 FqCobaltDrop();
326 }
327
328 return true;
329}
330
333{
334 NS_LOG_FUNCTION(this);
335
338
339 do
340 {
341 bool found = false;
342
343 while (!found && !m_newFlows.empty())
344 {
345 flow = m_newFlows.front();
346
347 if (flow->GetDeficit() <= 0)
348 {
349 NS_LOG_DEBUG("Increase deficit for new flow index " << flow->GetIndex());
350 flow->IncreaseDeficit(m_quantum);
351 flow->SetStatus(FqCobaltFlow::OLD_FLOW);
352 m_oldFlows.push_back(flow);
353 m_newFlows.pop_front();
354 }
355 else
356 {
357 NS_LOG_DEBUG("Found a new flow " << flow->GetIndex() << " with positive deficit");
358 found = true;
359 }
360 }
361
362 while (!found && !m_oldFlows.empty())
363 {
364 flow = m_oldFlows.front();
365
366 if (flow->GetDeficit() <= 0)
367 {
368 NS_LOG_DEBUG("Increase deficit for old flow index " << flow->GetIndex());
369 flow->IncreaseDeficit(m_quantum);
370 m_oldFlows.push_back(flow);
371 m_oldFlows.pop_front();
372 }
373 else
374 {
375 NS_LOG_DEBUG("Found an old flow " << flow->GetIndex() << " with positive deficit");
376 found = true;
377 }
378 }
379
380 if (!found)
381 {
382 NS_LOG_DEBUG("No flow found to dequeue a packet");
383 return nullptr;
384 }
385
386 item = flow->GetQueueDisc()->Dequeue();
387
388 if (!item)
389 {
390 NS_LOG_DEBUG("Could not get a packet from the selected flow queue");
391 if (!m_newFlows.empty())
392 {
393 flow->SetStatus(FqCobaltFlow::OLD_FLOW);
394 m_oldFlows.push_back(flow);
395 m_newFlows.pop_front();
396 }
397 else
398 {
399 flow->SetStatus(FqCobaltFlow::INACTIVE);
400 m_oldFlows.pop_front();
401 }
402 }
403 else
404 {
405 NS_LOG_DEBUG("Dequeued packet " << item->GetPacket());
406 }
407 } while (!item);
408
409 flow->IncreaseDeficit(item->GetSize() * -1);
410
411 return item;
412}
413
414bool
416{
417 NS_LOG_FUNCTION(this);
418 if (GetNQueueDiscClasses() > 0)
419 {
420 NS_LOG_ERROR("FqCobaltQueueDisc cannot have classes");
421 return false;
422 }
423
424 if (GetNInternalQueues() > 0)
425 {
426 NS_LOG_ERROR("FqCobaltQueueDisc cannot have internal queues");
427 return false;
428 }
429 // we are at initialization time. If the user has not set a quantum value,
430 // set the quantum to the MTU of the device (if any)
431 if (!m_quantum)
432 {
434 Ptr<NetDevice> dev;
435 // if the NetDeviceQueueInterface object is aggregated to a
436 // NetDevice, get the MTU of such NetDevice
437 if (ndqi && (dev = ndqi->GetObject<NetDevice>()))
438 {
439 m_quantum = dev->GetMtu();
440 NS_LOG_DEBUG("Setting the quantum to the MTU of the device: " << m_quantum);
441 }
442
443 if (!m_quantum)
444 {
445 NS_LOG_ERROR("The quantum parameter cannot be null");
446 return false;
447 }
448 }
449
451 {
452 NS_LOG_ERROR("The number of queues must be an integer multiple of the size "
453 "of the set of queues used by set associative hash");
454 return false;
455 }
456
457 // If UseL4S attribute is enabled then CE threshold must be set.
458 if (m_useL4s)
459 {
460 NS_ABORT_MSG_IF(m_ceThreshold == Time::Max(), "CE threshold not set");
461 if (!m_useEcn)
462 {
463 NS_LOG_WARN("Enabling ECN as L4S mode is enabled");
464 }
465 }
466 return true;
467}
468
469void
484
487{
488 NS_LOG_FUNCTION(this);
489
490 uint32_t maxBacklog = 0;
491 uint32_t index = 0;
493
494 /* Queue is full! Find the fat flow and drop packet(s) from it */
495 for (uint32_t i = 0; i < GetNQueueDiscClasses(); i++)
496 {
497 qd = GetQueueDiscClass(i)->GetQueueDisc();
498 uint32_t bytes = qd->GetNBytes();
499 if (bytes > maxBacklog)
500 {
501 maxBacklog = bytes;
502 index = i;
503 }
504 }
505
506 /* Our goal is to drop half of this fat flow backlog */
507 uint32_t len = 0;
508 uint32_t count = 0;
509 uint32_t threshold = maxBacklog >> 1;
510 qd = GetQueueDiscClass(index)->GetQueueDisc();
512
513 do
514 {
515 NS_LOG_DEBUG("Drop packet (overflow); count: " << count << " len: " << len
516 << " threshold: " << threshold);
517 item = qd->GetInternalQueue(0)->Dequeue();
519 len += item->GetSize();
520 } while (++count < m_dropBatchSize && len < threshold);
521
522 return index;
523}
524
525} // namespace ns3
Cobalt packet queue disc.
This class can be used to hold variables of floating point type such as 'double' or 'float'.
Definition double.h:31
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: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
Time MilliSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition nstime.h:1320
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 > MakeDoubleChecker()
Definition double.h:82
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 AttributeAccessor > MakeDoubleAccessor(T1 a1)
Definition double.h:32
Ptr< const AttributeChecker > MakeTimeChecker()
Helper to make an unbounded Time checker.
Definition nstime.h:1416