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 
29 namespace ns3 {
30 
31 NS_LOG_COMPONENT_DEFINE ("FqCoDelQueueDisc");
32 
33 NS_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 {
49  NS_LOG_FUNCTION (this);
50 }
51 
53 {
54  NS_LOG_FUNCTION (this);
55 }
56 
57 void
58 FqCoDelFlow::SetDeficit (uint32_t deficit)
59 {
60  NS_LOG_FUNCTION (this << deficit);
61  m_deficit = deficit;
62 }
63 
64 int32_t
66 {
67  NS_LOG_FUNCTION (this);
68  return m_deficit;
69 }
70 
71 void
73 {
74  NS_LOG_FUNCTION (this << deficit);
75  m_deficit += deficit;
76 }
77 
78 void
80 {
81  NS_LOG_FUNCTION (this);
82  m_status = status;
83 }
84 
87 {
88  NS_LOG_FUNCTION (this);
89  return m_status;
90 }
91 
92 
94 
96 {
97  static TypeId tid = TypeId ("ns3::FqCoDelQueueDisc")
98  .SetParent<QueueDisc> ()
99  .SetGroupName ("TrafficControl")
100  .AddConstructor<FqCoDelQueueDisc> ()
101  .AddAttribute ("Interval",
102  "The CoDel algorithm interval for each FQCoDel queue",
103  StringValue ("100ms"),
106  .AddAttribute ("Target",
107  "The CoDel algorithm target queue delay for each FQCoDel queue",
108  StringValue ("5ms"),
111  .AddAttribute ("MaxSize",
112  "The maximum number of packets accepted by this queue disc",
113  QueueSizeValue (QueueSize ("10240p")),
117  .AddAttribute ("Flows",
118  "The number of queues into which the incoming packets are classified",
119  UintegerValue (1024),
121  MakeUintegerChecker<uint32_t> ())
122  .AddAttribute ("DropBatchSize",
123  "The maximum number of packets dropped from the fat flow",
124  UintegerValue (64),
126  MakeUintegerChecker<uint32_t> ())
127  .AddAttribute ("Perturbation",
128  "The salt used as an additional input to the hash function used to classify packets",
129  UintegerValue (0),
131  MakeUintegerChecker<uint32_t> ())
132  ;
133  return tid;
134 }
135 
138  m_quantum (0)
139 {
140  NS_LOG_FUNCTION (this);
141 }
142 
144 {
145  NS_LOG_FUNCTION (this);
146 }
147 
148 void
150 {
151  NS_LOG_FUNCTION (this << quantum);
152  m_quantum = quantum;
153 }
154 
155 uint32_t
157 {
158  return m_quantum;
159 }
160 
161 bool
163 {
164  NS_LOG_FUNCTION (this << item);
165 
166  uint32_t h = 0;
167 
168  if (GetNPacketFilters () == 0)
169  {
170  h = item->Hash (m_perturbation) % m_flows;
171  }
172  else
173  {
174  int32_t ret = Classify (item);
175 
176  if (ret != PacketFilter::PF_NO_MATCH)
177  {
178  h = ret % m_flows;
179  }
180  else
181  {
182  NS_LOG_ERROR ("No filter has been able to classify this packet, drop it.");
184  return false;
185  }
186  }
187 
188  Ptr<FqCoDelFlow> flow;
189  if (m_flowsIndices.find (h) == m_flowsIndices.end ())
190  {
191  NS_LOG_DEBUG ("Creating a new flow queue with index " << h);
192  flow = m_flowFactory.Create<FqCoDelFlow> ();
194  qd->Initialize ();
195  flow->SetQueueDisc (qd);
196  AddQueueDiscClass (flow);
197 
199  }
200  else
201  {
202  flow = StaticCast<FqCoDelFlow> (GetQueueDiscClass (m_flowsIndices[h]));
203  }
204 
205  if (flow->GetStatus () == FqCoDelFlow::INACTIVE)
206  {
207  flow->SetStatus (FqCoDelFlow::NEW_FLOW);
208  flow->SetDeficit (m_quantum);
209  m_newFlows.push_back (flow);
210  }
211 
212  flow->GetQueueDisc ()->Enqueue (item);
213 
214  NS_LOG_DEBUG ("Packet enqueued into flow " << h << "; flow index " << m_flowsIndices[h]);
215 
216  if (GetCurrentSize () > GetMaxSize ())
217  {
218  FqCoDelDrop ();
219  }
220 
221  return true;
222 }
223 
226 {
227  NS_LOG_FUNCTION (this);
228 
229  Ptr<FqCoDelFlow> flow;
230  Ptr<QueueDiscItem> item;
231 
232  do
233  {
234  bool found = false;
235 
236  while (!found && !m_newFlows.empty ())
237  {
238  flow = m_newFlows.front ();
239 
240  if (flow->GetDeficit () <= 0)
241  {
242  flow->IncreaseDeficit (m_quantum);
243  flow->SetStatus (FqCoDelFlow::OLD_FLOW);
244  m_oldFlows.push_back (flow);
245  m_newFlows.pop_front ();
246  }
247  else
248  {
249  NS_LOG_DEBUG ("Found a new flow with positive deficit");
250  found = true;
251  }
252  }
253 
254  while (!found && !m_oldFlows.empty ())
255  {
256  flow = m_oldFlows.front ();
257 
258  if (flow->GetDeficit () <= 0)
259  {
260  flow->IncreaseDeficit (m_quantum);
261  m_oldFlows.push_back (flow);
262  m_oldFlows.pop_front ();
263  }
264  else
265  {
266  NS_LOG_DEBUG ("Found an old flow with positive deficit");
267  found = true;
268  }
269  }
270 
271  if (!found)
272  {
273  NS_LOG_DEBUG ("No flow found to dequeue a packet");
274  return 0;
275  }
276 
277  item = flow->GetQueueDisc ()->Dequeue ();
278 
279  if (!item)
280  {
281  NS_LOG_DEBUG ("Could not get a packet from the selected flow queue");
282  if (!m_newFlows.empty ())
283  {
284  flow->SetStatus (FqCoDelFlow::OLD_FLOW);
285  m_oldFlows.push_back (flow);
286  m_newFlows.pop_front ();
287  }
288  else
289  {
290  flow->SetStatus (FqCoDelFlow::INACTIVE);
291  m_oldFlows.pop_front ();
292  }
293  }
294  else
295  {
296  NS_LOG_DEBUG ("Dequeued packet " << item->GetPacket ());
297  }
298  } while (item == 0);
299 
300  flow->IncreaseDeficit (item->GetSize () * -1);
301 
302  return item;
303 }
304 
305 bool
307 {
308  NS_LOG_FUNCTION (this);
309  if (GetNQueueDiscClasses () > 0)
310  {
311  NS_LOG_ERROR ("FqCoDelQueueDisc cannot have classes");
312  return false;
313  }
314 
315  if (GetNInternalQueues () > 0)
316  {
317  NS_LOG_ERROR ("FqCoDelQueueDisc cannot have internal queues");
318  return false;
319  }
320 
321  // we are at initialization time. If the user has not set a quantum value,
322  // set the quantum to the MTU of the device (if any)
323  if (!m_quantum)
324  {
326  Ptr<NetDevice> dev;
327  // if the NetDeviceQueueInterface object is aggregated to a
328  // NetDevice, get the MTU of such NetDevice
329  if (ndqi && (dev = ndqi->GetObject<NetDevice> ()))
330  {
331  m_quantum = dev->GetMtu ();
332  NS_LOG_DEBUG ("Setting the quantum to the MTU of the device: " << m_quantum);
333  }
334 
335  if (!m_quantum)
336  {
337  NS_LOG_ERROR ("The quantum parameter cannot be null");
338  return false;
339  }
340  }
341 
342  return true;
343 }
344 
345 void
347 {
348  NS_LOG_FUNCTION (this);
349 
350  m_flowFactory.SetTypeId ("ns3::FqCoDelFlow");
351 
352  m_queueDiscFactory.SetTypeId ("ns3::CoDelQueueDisc");
356 }
357 
358 uint32_t
360 {
361  NS_LOG_FUNCTION (this);
362 
363  uint32_t maxBacklog = 0, index = 0;
364  Ptr<QueueDisc> qd;
365 
366  /* Queue is full! Find the fat flow and drop packet(s) from it */
367  for (uint32_t i = 0; i < GetNQueueDiscClasses (); i++)
368  {
369  qd = GetQueueDiscClass (i)->GetQueueDisc ();
370  uint32_t bytes = qd->GetNBytes ();
371  if (bytes > maxBacklog)
372  {
373  maxBacklog = bytes;
374  index = i;
375  }
376  }
377 
378  /* Our goal is to drop half of this fat flow backlog */
379  uint32_t len = 0, count = 0, threshold = maxBacklog >> 1;
380  qd = GetQueueDiscClass (index)->GetQueueDisc ();
381  Ptr<QueueDiscItem> item;
382 
383  do
384  {
385  item = qd->GetInternalQueue (0)->Dequeue ();
387  len += item->GetSize ();
388  } while (++count < m_dropBatchSize && len < threshold);
389 
390  return index;
391 }
392 
393 } // namespace ns3
void SetDeficit(uint32_t deficit)
Set the deficit for this flow.
Ptr< const AttributeChecker > MakeStringChecker(void)
Definition: string.cc:30
A FqCoDel packet queue disc.
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:73
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
Class for representing queue sizes.
Definition: queue-size.h:94
FlowStatus
Used to determine the status of this flow queue.
uint32_t m_quantum
Deficit assigned to flows at each round.
void AddQueueDiscClass(Ptr< QueueDiscClass > qdClass)
Add a queue disc class to the tail of the list of classes.
Definition: queue-disc.cc:634
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:729
static const int PF_NO_MATCH
Standard value used by packet filters to indicate that no match was possible.
Definition: packet-filter.h:48
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
Hold variables of type string.
Definition: string.h:41
QueueSizeUnit
Enumeration of the operating modes of queues.
Definition: queue-size.h:42
QueueSize GetCurrentSize(void)
Get the current size of the queue disc in bytes, if operating in bytes mode, or packets, otherwise.
Definition: queue-disc.cc:523
uint32_t FqCoDelDrop(void)
Drop a packet from the head of the queue with the largest current byte count.
uint32_t m_dropBatchSize
Max number of packets dropped from the fat flow.
int32_t GetDeficit(void) const
Get the deficit for this flow.
static TypeId GetTypeId(void)
Get the type ID.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
void SetTypeId(TypeId tid)
Set the TypeId of the Objects to be created by this factory.
uint32_t GetNBytes(void) const
Get the amount of bytes stored by the queue disc.
Definition: queue-disc.cc:447
QueueDisc is an abstract base class providing the interface and implementing the operations common to...
Definition: queue-disc.h:181
Ptr< NetDeviceQueueInterface > GetNetDeviceQueueInterface(void) const
Definition: queue-disc.cc:546
FqCoDelFlow()
FqCoDelFlow constructor.
void SetStatus(FlowStatus status)
Set the status for this flow.
A flow queue used by the FqCoDel queue disc.
int32_t m_deficit
the deficit for this flow
uint32_t m_flows
Number of flow queues.
Ptr< Object > Create(void) const
Create an Object instance of the configured TypeId.
Ptr< InternalQueue > GetInternalQueue(std::size_t i) const
Get the i-th internal queue.
Definition: queue-disc.cc:601
Hold an unsigned integer type.
Definition: uinteger.h:44
Use number of packets for queue size.
Definition: queue-size.h:44
uint32_t GetQuantum(void) const
Get the quantum value.
uint32_t m_perturbation
hash perturbation value
virtual bool CheckConfig(void)
Check whether the current configuration is correct.
Ptr< const AttributeAccessor > MakeQueueSizeAccessor(T1 a1)
Definition: queue-size.h:221
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:675
Ptr< QueueDiscClass > GetQueueDiscClass(std::size_t i) const
Get the i-th queue disc class.
Definition: queue-disc.cc:662
static constexpr const char * UNCLASSIFIED_DROP
No packet filter able to classify packet.
QueueDiscClass is the base class for classes that are included in a queue disc.
Definition: queue-disc.h:49
Ptr< const AttributeChecker > MakeQueueSizeChecker(void)
Definition: queue-size.cc:29
std::list< Ptr< FqCoDelFlow > > m_newFlows
The list of new flows.
virtual Ptr< QueueDiscItem > DoDequeue(void)
This function actually extracts a packet from the queue disc.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
std::size_t GetNQueueDiscClasses(void) const
Get the number of queue disc classes.
Definition: queue-disc.cc:669
std::string m_interval
CoDel interval attribute.
void SetQuantum(uint32_t quantum)
Set the quantum value.
std::string m_target
CoDel target attribute.
ObjectFactory m_queueDiscFactory
Factory to create a new queue.
static TypeId GetTypeId(void)
Get the type ID.
std::map< uint32_t, uint32_t > m_flowsIndices
Map with the index of class for each flow.
FqCoDelQueueDisc()
FqCoDelQueueDisc constructor.
void Set(std::string name, const AttributeValue &value)
Set an attribute to be set during construction.
virtual void InitializeParams(void)
Initialize parameters (if any) before the first packet is enqueued.
QueueSize GetMaxSize(void) const
Get the maximum size of the queue disc.
Definition: queue-disc.cc:454
QueueDiscSizePolicy
Enumeration of the available policies to handle the queue disc size.
Definition: queue-disc.h:103
Used by queue discs with multiple internal queues/child queue discs.
Definition: queue-disc.h:107
Network layer to device interface.
Definition: net-device.h:95
std::size_t GetNPacketFilters(void) const
Get the number of packet filters.
Definition: queue-disc.cc:628
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:273
FlowStatus GetStatus(void) const
Get the status of this flow.
bool SetMaxSize(QueueSize size)
Set the maximum size of the queue disc.
Definition: queue-disc.cc:482
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:768
std::list< Ptr< FqCoDelFlow > > m_oldFlows
The list of old flows.
virtual bool DoEnqueue(Ptr< QueueDiscItem > item)
This function actually enqueues a packet into the queue disc.
#define NS_LOG_ERROR(msg)
Use NS_LOG to output a message of level LOG_ERROR.
Definition: log.h:257
static constexpr const char * OVERLIMIT_DROP
Overlimit dropped packets.
Ptr< const AttributeAccessor > MakeStringAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method...
Definition: string.h:42
void IncreaseDeficit(int32_t deficit)
Increase the deficit for this flow.
Ptr< const AttributeAccessor > MakeUintegerAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method...
Definition: uinteger.h:45
FlowStatus m_status
the status of this flow
a unique identifier for an interface.
Definition: type-id.h:58
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:923
Inactive Period or unslotted CSMA-CA.
Definition: lr-wpan-mac.h:92
void Initialize(void)
Invoke DoInitialize on all Objects aggregated to this one.
Definition: object.cc:183
ObjectFactory m_flowFactory
Factory to create a new flow.
std::size_t GetNInternalQueues(void) const
Get the number of internal queues.
Definition: queue-disc.cc:608