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 ("PacketLimit",
112  "The hard limit on the real queue size, measured in packets",
113  UintegerValue (10 * 1024),
115  MakeUintegerChecker<uint32_t> ())
116  .AddAttribute ("Flows",
117  "The number of queues into which the incoming packets are classified",
118  UintegerValue (1024),
120  MakeUintegerChecker<uint32_t> ())
121  .AddAttribute ("DropBatchSize",
122  "The maximum number of packets dropped from the fat flow",
123  UintegerValue (64),
125  MakeUintegerChecker<uint32_t> ())
126  ;
127  return tid;
128 }
129 
131  : m_quantum (0)
132 {
133  NS_LOG_FUNCTION (this);
134 }
135 
137 {
138  NS_LOG_FUNCTION (this);
139 }
140 
141 void
143 {
144  NS_LOG_FUNCTION (this << quantum);
145  m_quantum = quantum;
146 }
147 
148 uint32_t
150 {
151  return m_quantum;
152 }
153 
154 bool
156 {
157  NS_LOG_FUNCTION (this << item);
158 
159  int32_t ret = Classify (item);
160 
161  if (ret == PacketFilter::PF_NO_MATCH)
162  {
163  NS_LOG_ERROR ("No filter has been able to classify this packet, drop it.");
165  return false;
166  }
167 
168  uint32_t h = ret % m_flows;
169 
170  Ptr<FqCoDelFlow> flow;
171  if (m_flowsIndices.find (h) == m_flowsIndices.end ())
172  {
173  NS_LOG_DEBUG ("Creating a new flow queue with index " << h);
174  flow = m_flowFactory.Create<FqCoDelFlow> ();
176  qd->Initialize ();
177  flow->SetQueueDisc (qd);
178  AddQueueDiscClass (flow);
179 
181  }
182  else
183  {
184  flow = StaticCast<FqCoDelFlow> (GetQueueDiscClass (m_flowsIndices[h]));
185  }
186 
187  if (flow->GetStatus () == FqCoDelFlow::INACTIVE)
188  {
189  flow->SetStatus (FqCoDelFlow::NEW_FLOW);
190  flow->SetDeficit (m_quantum);
191  m_newFlows.push_back (flow);
192  }
193 
194  flow->GetQueueDisc ()->Enqueue (item);
195 
196  NS_LOG_DEBUG ("Packet enqueued into flow " << h << "; flow index " << m_flowsIndices[h]);
197 
198  if (GetNPackets () > m_limit)
199  {
200  FqCoDelDrop ();
201  }
202 
203  return true;
204 }
205 
208 {
209  NS_LOG_FUNCTION (this);
210 
211  Ptr<FqCoDelFlow> flow;
212  Ptr<QueueDiscItem> item;
213 
214  do
215  {
216  bool found = false;
217 
218  while (!found && !m_newFlows.empty ())
219  {
220  flow = m_newFlows.front ();
221 
222  if (flow->GetDeficit () <= 0)
223  {
224  flow->IncreaseDeficit (m_quantum);
225  flow->SetStatus (FqCoDelFlow::OLD_FLOW);
226  m_oldFlows.push_back (flow);
227  m_newFlows.pop_front ();
228  }
229  else
230  {
231  NS_LOG_DEBUG ("Found a new flow with positive deficit");
232  found = true;
233  }
234  }
235 
236  while (!found && !m_oldFlows.empty ())
237  {
238  flow = m_oldFlows.front ();
239 
240  if (flow->GetDeficit () <= 0)
241  {
242  flow->IncreaseDeficit (m_quantum);
243  m_oldFlows.push_back (flow);
244  m_oldFlows.pop_front ();
245  }
246  else
247  {
248  NS_LOG_DEBUG ("Found an old flow with positive deficit");
249  found = true;
250  }
251  }
252 
253  if (!found)
254  {
255  NS_LOG_DEBUG ("No flow found to dequeue a packet");
256  return 0;
257  }
258 
259  item = flow->GetQueueDisc ()->Dequeue ();
260 
261  if (!item)
262  {
263  NS_LOG_DEBUG ("Could not get a packet from the selected flow queue");
264  if (!m_newFlows.empty ())
265  {
266  flow->SetStatus (FqCoDelFlow::OLD_FLOW);
267  m_oldFlows.push_back (flow);
268  m_newFlows.pop_front ();
269  }
270  else
271  {
272  flow->SetStatus (FqCoDelFlow::INACTIVE);
273  m_oldFlows.pop_front ();
274  }
275  }
276  else
277  {
278  NS_LOG_DEBUG ("Dequeued packet " << item->GetPacket ());
279  }
280  } while (item == 0);
281 
282  flow->IncreaseDeficit (-item->GetSize ());
283 
284  return item;
285 }
286 
289 {
290  NS_LOG_FUNCTION (this);
291 
292  Ptr<FqCoDelFlow> flow;
293 
294  if (!m_newFlows.empty ())
295  {
296  flow = m_newFlows.front ();
297  }
298  else
299  {
300  if (!m_oldFlows.empty ())
301  {
302  flow = m_oldFlows.front ();
303  }
304  else
305  {
306  return 0;
307  }
308  }
309 
310  return flow->GetQueueDisc ()->Peek ();
311 }
312 
313 bool
315 {
316  NS_LOG_FUNCTION (this);
317  if (GetNQueueDiscClasses () > 0)
318  {
319  NS_LOG_ERROR ("FqCoDelQueueDisc cannot have classes");
320  return false;
321  }
322 
323  if (GetNPacketFilters () == 0)
324  {
325  NS_LOG_ERROR ("FqCoDelQueueDisc needs at least a packet filter");
326  return false;
327  }
328 
329  if (GetNInternalQueues () > 0)
330  {
331  NS_LOG_ERROR ("FqCoDelQueueDisc cannot have internal queues");
332  return false;
333  }
334 
335  return true;
336 }
337 
338 void
340 {
341  NS_LOG_FUNCTION (this);
342 
343  // we are at initialization time. If the user has not set a quantum value,
344  // set the quantum to the MTU of the device
345  if (!m_quantum)
346  {
347  Ptr<NetDevice> device = GetNetDevice ();
348  NS_ASSERT_MSG (device, "Device not set for the queue disc");
349  m_quantum = device->GetMtu ();
350  NS_LOG_DEBUG ("Setting the quantum to the MTU of the device: " << m_quantum);
351  }
352 
353  m_flowFactory.SetTypeId ("ns3::FqCoDelFlow");
354 
355  m_queueDiscFactory.SetTypeId ("ns3::CoDelQueueDisc");
357  m_queueDiscFactory.Set ("MaxPackets", UintegerValue (m_limit + 1));
360 }
361 
362 uint32_t
364 {
365  NS_LOG_FUNCTION (this);
366 
367  uint32_t maxBacklog = 0, index = 0;
368  Ptr<QueueDisc> qd;
369 
370  /* Queue is full! Find the fat flow and drop packet(s) from it */
371  for (uint32_t i = 0; i < GetNQueueDiscClasses (); i++)
372  {
373  qd = GetQueueDiscClass (i)->GetQueueDisc ();
374  uint32_t bytes = qd->GetNBytes ();
375  if (bytes > maxBacklog)
376  {
377  maxBacklog = bytes;
378  index = i;
379  }
380  }
381 
382  /* Our goal is to drop half of this fat flow backlog */
383  uint32_t len = 0, count = 0, threshold = maxBacklog >> 1;
384  qd = GetQueueDiscClass (index)->GetQueueDisc ();
385  Ptr<QueueDiscItem> item;
386 
387  do
388  {
389  item = qd->GetInternalQueue (0)->Dequeue ();
391  len += item->GetSize ();
392  } while (++count < m_dropBatchSize && len < threshold);
393 
394  return index;
395 }
396 
397 } // 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.
uint32_t GetNQueueDiscClasses(void) const
Get the number of queue disc classes.
Definition: queue-disc.cc:557
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 "...
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:525
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:609
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
uint32_t GetNBytes(void) const
Get the amount of bytes stored by the queue disc.
Definition: queue-disc.cc:437
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.
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:201
void SetTypeId(TypeId tid)
Set the TypeId of the Objects to be created by this factory.
QueueDisc is an abstract base class providing the interface and implementing the operations common to...
Definition: queue-disc.h:151
FqCoDelFlow()
FqCoDelFlow constructor.
void SetStatus(FlowStatus status)
Set the status for this flow.
A flow queue used by the FqCoDel queue disc.
Ptr< InternalQueue > GetInternalQueue(uint32_t i) const
Get the i-th internal queue.
Definition: queue-disc.cc:492
int32_t m_deficit
the deficit for this flow
uint32_t m_flows
Number of flow queues.
uint32_t GetNInternalQueues(void) const
Get the number of internal queues.
Definition: queue-disc.cc:499
Hold variables of type enum.
Definition: enum.h:54
virtual Ptr< const QueueDiscItem > DoPeek(void) const
This function returns a copy of the next packet the queue disc will extract.
Ptr< Object > Create(void) const
Create an Object instance of the configured TypeId.
Hold an unsigned integer type.
Definition: uinteger.h:44
FlowStatus GetStatus(void) const
Get the status of this flow.
virtual bool CheckConfig(void)
Check whether the current configuration is correct.
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:563
uint32_t GetNPacketFilters(void) const
Get the number of packet filters.
Definition: queue-disc.cc:519
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:48
std::list< Ptr< FqCoDelFlow > > m_newFlows
The list of new flows.
int32_t GetDeficit(void) const
Get the deficit for this flow.
uint32_t GetQuantum(void) const
Get the quantum value.
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::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.
#define NS_ASSERT_MSG(condition, message)
At runtime, in debugging builds, if this condition is not true, the program prints the message to out...
Definition: assert.h:90
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:269
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:648
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.
Use number of packets for maximum queue disc size.
#define NS_LOG_ERROR(msg)
Use NS_LOG to output a message of level LOG_ERROR.
Definition: log.h:253
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.
FlowStatus
Used to determine the status of this flow queue.
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
uint32_t m_limit
Maximum number of packets in the queue disc.
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:914
Ptr< NetDevice > GetNetDevice(void) const
Get the NetDevice on which this queue discipline is installed.
Definition: queue-disc.cc:451
void Initialize(void)
Invoke DoInitialize on all Objects aggregated to this one.
Definition: object.cc:183
Ptr< QueueDiscClass > GetQueueDiscClass(uint32_t i) const
Get the i-th queue disc class.
Definition: queue-disc.cc:550
ObjectFactory m_flowFactory
Factory to create a new flow.
uint32_t GetNPackets(void) const
Get the number of packets stored by the queue disc.
Definition: queue-disc.cc:430